Ist

15

Was passiert, wenn wir so definieren, dass anstelle einer Polytime-Turing-Maschine / Polysize-Schaltung eine Logspace-Turing-Maschine oder eine -Schaltung das Problem codiert?PPADPPADAC0AC0

Kürzlich stellte sich heraus , dass es wichtig war, schnellere Algorithmen für die Schaltungserfüllbarkeit für kleine Schaltungen . frage ich mich, was mit den korrigierten Versionen von .PPADPPAD

domotorp
quelle
Buss und Johnson, "Propositional proofs and reductions between NP search problems", beweisen, dass PPAD unter Turing reductions geschlossen ist, und ich bin mir ziemlich sicher, dass eine geringfügige Modifikation des Arguments die Entsprechung von PPAD mit seiner (einheitlichen) AC ^ 0-Version ergibt .
Emil Jeřábek unterstützt Monica
@Emil: Vielen Dank für den Vorschlag, leider sind die Begriffe in diesem Artikel für mich unverständlich. Ich wäre dankbar, wenn mir jemand die Auswirkungen mitteilen könnte. Lassen Sie mich auch hier auf seinen Preprint verlinken
domotorp

Antworten:

10

Ja, . (Hier und unten gehe ich davon aus, dass als eine einheitliche Klasse definiert ist. Natürlich würden wir bei einer uneinheitlichen \ ac nur \ mathrm {PPAD / poly} erhalten .)A C 0 P A D = P P A D A C 0 A C 0 P P A D / P o l yAC0PAD=PPADAC0AC0PPAD/poly

Die Grundidee ist ganz einfach: A C 0AC0 kann einen Schritt einer Turing-Maschinenberechnung ausführen, daher können wir eine polynomzeitberechnbare Kante durch eine polynomlange Linie von A C 0AC0 -berechnbaren Kanten simulieren. Durch eine weitere Erweiterung der Idee könnte man mit einem PPAD-Orakel in Polyzeit berechenbare Kanten simulieren, dh PPAD wird unter Turing-Reduzierbarkeit geschlossen; Dieses Argument findet sich in Buss und Johnson .

Es gibt in der Literatur viele äquivalente Definitionen von PPAD, die sich in verschiedenen Details unterscheiden. Ein NP-Suchproblem liegt in PPAD vor, wenn es ein Polynom und Polynomzeitfunktionen , und mit den folgenden Eigenschaften gibt. Für jeden Eingang der Länge , und stellen einen gerichteten Graphen ohne Selbstschleifen wo , und jeder Knoten hat Ein- grad und out-grad höchstens . Die Darstellung ist so, dass wennS p ( n ) f ( x , u ) g ( x , u ) h ( x , u ) x n f g G x = ( V x , E x ) V x = { 0 , 1 } p ( n ) 1 ( u , v ) E x f ( xSp(n)f(x,u)g(x,u)h(x,u)xnfgGx=(Vx,Ex)Vx={0,1}p(n)1(u,v)Ex, dann ist und ; wenn Grad , ist ; und wenn Grad , ist ., u ) = v g ( x , v ) = u u 0 f ( x , u ) = u u 0 g ( x , u ) = uf(x,u)=vg(x,v)=uu0f(x,u)=uu0g(x,u)=u

Der Knoten ist eine Quelle (dh er hat einen In-Grad und einen Out-Grad ). Wenn eine Quelle oder Senke (in Grad , out Grad ) als , dann ist eine Lösung für .0 p ( n )V x 0 1 u V x 1 0 0 p ( n ) h ( x , u ) S ( x )0p(n)Vx01uVx100p(n)h(x,u)S(x)

Wir können ähnliche Weise definieren, außer dass in .AC0PADAC0PADf,g,hf,g,hFAC0FAC0

Ich werde in der Konstruktion der Einfachheit halber ignorieren . (Es ist nicht schwer zu zeigen, dass man es für eine Projektion halten kann, daherhh A C 0 -berechenbar.)AC0

Man betrachte also ein PPAD-Problem S, das durch f und g definiert ist , und behebe Turing-Maschinen, die f und g in der Zeit q ( n ) berechnen . Für jedes x definieren wir einen gerichteten Graphen G ' x = ( V ' x , E ' x ), dessen Eckpunkte Folgen der folgenden Form sind:Sfgfgq(n)xGx=(Vx,Ex)

  • ( 0 , u , c 1 , ... , c k ) , wobei u V x , 0 k q ( n ) und c 1 , ... , c k sind die ersten k - Konfigurationen in der Berechnung von f ( x , u ) .(0,u,c1,,ck)uVx0kq(n)c1,,ckkf(x,u)

  • ( 0 , u , c 1 , ... , C q ( n ) , v , d 1 , ... , d k ) , wobei u , v V x , 0 k q ( n ) , f ( x , u ) = v , c 1 , ... , c q ((0,u,c1,,cq(n),v,d1,,dk)u,vVx0kq(n)f(x,u)=vn ) ist die vollständige Berechnung vonf(x,u)und d 1 ,..., d k sind die erstenkSchritte bei der Berechnung vong(x,v).c1,,cq(n)f(x,u)d1,,dkkg(x,v)

  • ( 1 , v , d 1 , ... , d k ) , wobei 0 p ( n )v V x , 0 k q ( n ) , und d 1 , ... , d k sind die ersten k Konfigurationen in dem Berechnung von g ( x , v ) .(1,v,d1,,dk)0p(n)vVx0kq(n)d1,,dkkg(x,v)

  • ( 1 , v , d 1 , ... , d q ( n ) , u , c 1 , ... , c k ) , wobei u , v V x , v 0 p ( n ) , 0 k q ( n ) , g ( x , v ) = u ,(1,v,d1,,dq(n),u,c1,,ck)u,vVxv0p(n)0kq(n)g(x,v)=ud 1 , , d q ( n ) ist die Berechnung von g ( x , v ) , und c 1 , , c k sind die ersten k Schritte bei der Berechnung von f ( x , u ) .d1,,dq(n)g(x,v)c1,,ckk

E ' x besteht aus den Kanten in V ' x × V ' x der folgenden Arten:

  • ( 0 , u , c 1 , , c k ) ( 0 , u , c 1 , , c k + 1 )

  • ( 0 , u , c 1 , ... , c q ( n ) ) ( 0 , u , c 1 , ... , c q ( n ) , v )

  • ( 0 , u , c 1 , , c q ( n ) , v , d 1 , , d k ) ( 0 , u , c 1 , , c q ( n ) , v , d 1 , , d k + 1 )

  • ( 0 , u , c 1 , ... , c q ( n ) , v , d 1 , ... , d q ( n ) ) ( 1 , v , d 1 , ... , d q ( n ) , u , c 1 , , C q ( n ) ) wenn f( u ) = v und g ( v ) = u (dh entweder ( u , v ) E x oder u = v ist ein isolierter Scheitelpunkt)

  • ( 1 , v , d 1 , ... , d q ( n ) , u , c 1 , ... , c k + 1 ) ( 1 , v , d 1 , ... , d q ( n ) , u , c 1 , , C k )

  • ( 1 , v , d 1 , ... , d q ( n ) , u ) ( 1 , v , d 1 , ... , d q ( n ) )

  • ( 1 , v , d 1 , , d k + 1 ) ( 1 , v , d 1 , , d k )

  • (1,u)(0,u)

Formally, let r(n) be a polynomial bounding the lengths of binary representations of all the sequences above (such that we can extend or shorten sequences, and extract their elements with AC0-functions); we actually put Vx={0,1}r(n), and we let all vertices except the above-mentioned sequences to be isolated.

It is easy to see that the functions f, g representing Gx are AC0-computable: in particular, we can test in AC0 whether c1,,ck is a valid partial computation of f(x,u), we can compute ck+1 from ck, and we can extract the value of f(x,u) from cq(n).

The sinks in Gx are nodes of the form (0,u,c1,,cq(n),u,d1,,dq(n)) where u is a sink in Gx. Likewise, sources are (1,v,d1,,dq(n),v,c1,,cq(n)) where v is a source in Gx, except that in the special case v=0p(n), we have pruned the line early and the corresponding source in Gx is just (0,0p(n)). We can assume the encoding of sequences is done in such a way that (0,0p(n))=0r(n).

Thus, f and g define an AC0PAD problem S, and we can extract a solution to S(x) from a solution to S(x) by an AC0-function h which outputs the second component of a sequence.

Emil Jeřábek supports Monica
quelle