algorithm - 多項式時間短縮推移性証明

Question

次のステートメントで「アルファベット」が何を意味するかを誰かが明確にできるかどうかを確認しようとしています.

「思い出してください: 多項式時間削減 ≤p の場合、L ≤p M は、計算可能な関数 f があることを意味します: L のアルファベット→M のアルファベットで、x∈L iff f(x)∈M となります。」

多項式簡約の推移性の証明です。

Answer 1

アルファベットは、言語 (この場合は L または M) を構成する記号のセットです。