Warum sind P und P / Poly nicht trivial gleich?

10

Die Definition von P ist eine Sprache, die durch einen Polynomzeitalgorithmus bestimmt werden kann. Unter der Definition von P / Poly kann eine Sprache verstanden werden, die von einer Schaltung mit Polynomgröße bestimmt werden kann (siehe http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Warum kann eine polynomgroße Schaltung nicht in Polynomzeit simuliert werden?

dcw
quelle
4
P / Poly kann unentscheidbare Sprachen berechnen (Übung).
Yuval Filmus
Danke, aber was ist falsch an meinem Argument, dass eine Schaltung mit Polynomgröße in Polynomzeit simuliert werden kann?
dcw
3
Es ist falsch. Die Schaltungen mit Polynomgröße für unterschiedliche Eingangslängen können radikal unterschiedlich sein und können daher nicht alle von einer einzelnen Turing-Maschine beschrieben werden.
Yuval Filmus
Danke, aber wo in der Definition P steht, dass wir auf eine einzelne Turing-Maschine beschränkt sind? Alle Definitionen, die ich gesehen habe, sind wie in mathworld.wolfram.com/PolynomialTime.html
dcw
3
@dcw Eine Sprache ist in P, wenn es eine Turing-Maschine gibt, so dass ...
David Richerby

Antworten:

19

Der Punkt bei Schaltungen ist, dass eine Schaltung eine feste Anzahl von Eingängen hat. Dies bedeutet, dass wir zum Definieren einer Sprache eine Familie von Schaltkreisen C.0,C.1,C.2, benötigen , sodass der Schaltkreis  C.ich für jedes i angibt, welche Zeichenfolgen der Länge  ich in der Sprache sind  . Dies erfordert keine Beziehung zwischen den Schaltkreisen C i und  C i + 1 : Sie können völlig unterschiedlich sein. Insbesondere können Sie für jede Menge  S N die Deklaration C i setzenichC.ichC.ich+1S.N.C.ich=true , wennichS. undC.ich=feinlse fürichS. . Auch wennS.  unentscheidbar ist!

Im Gegensatz dazu ist eine Sprache in  P. wenn es eine einzelne Turing-Maschine gibt, die Ihnen sagt, ob jede mögliche Eingabe jeder möglichen Länge in der Sprache ist. Jetzt können Sie keine lustigen Spiele über Eingaben unterschiedlicher Länge spielen.

Sie haben Recht, dass wir jeden festen Schaltkreis in P. auswerten können  . Aber das ist nicht unbedingt genug , um eine Sprache in entscheiden , P./.pÖly . Dazu müssten wir zuerst die Länge des Eingangs berechnen und dann bestimmen, welche Schaltung  C.ich ausgewertet werden muss, und dann die Schaltung auswerten. Wie das obige Beispiel zeigt, ist der Teil "Bestimmen, welche Schaltung" möglicherweise nicht einmal berechenbar, geschweige denn in Polynomzeit berechenbar.

David Richerby
quelle
1
Es ist Jahre her, seit ich das alles studiert habe und ich hatte (fast) die Definition von vergessen , aber das Lesen dieser Antwort brachte alles zurück: Ich erinnere mich, dass ich die gleiche Verwirrung hatte, als ich zum ersten Mal auf die Definition stieß und zu der kam gleiche Auflösung / Verständnis. :-)P./.pÖly
ShreevatsaR