多項式時間言語に多項式サイズの回路があるのはなぜですか？

Question

PSがPSCPACEのサブセットである理由を理解したいのですが、それが多項式時間のランゲージには多項式サイズの回路がある理由です。私はのような多くの証拠を読みました これは2-3ページにあります, 、しかし、すべての証明は、クックレビン定理で使用されているのと同じ手法を使用して、Nビット入力XでのMの計算を多項式サイズの回路に変換します。

私が理解していないのは、結果の回路が入力xに依存しているということです。なぜなら、回路に変換されているのは特定の入力xでのMの計算だからです。 Psizeの定義により、同じ回路が固定長のすべての入力に対して動作する必要があるため、特定の入力に依存しません。

それでは、ポリタイム決定論的チューリングマシンのポリサイズのサーキットファミリを作成するプロセスは、どのように機能しますか？

Answer 1

Cook-Levinは、特定のサイズのすべての入力に対して1つの回路を提供します。したがって、回路は入力$ x $に依存しますが、入力のサイズにのみ依存します。したがって、実行時間$ t $と数$ n $（入力のサイズ）のtm $ m $を与えられた場合、クックレビンは、すべての入力で問題を解決する約$ t^2 $の回路$ c_n $を約$ t^2 $に与えますサイズ$ n $の。回路$ c_n $は、$ m $の入力のビットに依存しませんが、回路の入力ビット数になるため、入力ビットの数を知る必要があります。

Answer 2

直感的には、多項式サイズの問題には、アルゴリズム/回路の各ステップには一定の時間がかかるため、少なくとも多項式サイズの回路が必要です。回路が多項式時間未満で言語の要素を検証できる場合、アルゴリズムも行うことができます。