Warum hat eine Polynomzeitsprache eine Polynomgröße?

Question

Ich möchte verstehen, warum P eine Untergruppe von PSCPACE ist. Deshalb hat eine Polynom-Zeit-Langauge eine Polynomgröße. Ich habe viele Beweise wie gelesen wie Dieser hier auf Seite 2-3, Aber alle Beweise verwenden dieselbe Technik, die im Cook-Levin-Theorem verwendet wird, um die Berechnung von m auf einem n-Bit-Eingang X in eine Polynomgröße zu konvertieren.

Was ich nicht verstehe ist, dass der resultierende Schaltkreis vom Eingang X abhängt, da das, was in eine Schaltung umgewandelt wird, die Berechnung von m auf dem spezifischen Eingang x ist. Per Definition von PSIZE muss dieselbe Schaltung für alle Eingänge in einer festen Länge funktionieren und hängt daher nicht von einer bestimmten Eingabe ab.

Wie funktioniert der Prozess der Erstellung einer polygroßen Kreisfamilie für eine deterministische Turing-Maschine mit Poly-Zeit genau?

Answer 1

Cook-Levin gibt einen Stromkreis für alle Eingänge einer bestimmten Größe. Obwohl die Schaltung von der Eingabe $ x $ abhängt, hängt sie nur von der Größe des Eingangs ab. Angesichts des TM $ m $ mit Laufzeit $ t $ und einer Nummer $ n $ (die Größe der Eingabe) gibt Cook-Levin einer Schaltung $ c_n $ von ungefähr $ t^2 $, die das Problem bei allen Eingaben löst von Größe $ n $. Die Schaltung $ c_n $ hängt nicht von den Bits der Eingabe für $ M $ ab. Wir müssen jedoch die Anzahl der Eingangsbits kennen, da dies die Anzahl der Eingangsbits für die Schaltung sein wird.

Answer 2

Intuitiv erfordert ein Polynomgrößenproblem mindestens eine Polynomgröße, da jeder Schritt im Algorithmus/Schaltkreis eine bestimmte Zeit erfordert. Wenn die Schaltung ein Element der Sprache in weniger als Polynomzeit überprüfen könnte, kann dies auch ein Algorithmus gemacht werden.