Was passiert, wenn wir so definieren, dass anstelle einer Polytime-Turing-Maschine / Polysize-Schaltung eine Logspace-Turing-Maschine oder eine -Schaltung das Problem codiert?PPAD
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 .PPAD
Antworten:
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 ( xS p(n) f(x,u) g(x,u) h(x,u) x n f g Gx=(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)=v g(x,v)=u u 0 f(x,u)=u u 0 g(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)∈Vx 0 1 u∈Vx 1 0 0p(n) h(x,u) S(x)
Wir können ähnliche Weise definieren, außer dass in .AC0PADAC0PAD f,g,hf,g,h FAC0FAC0
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:S f g f g q(n) x G′x=(V′x,E′x)
( 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) u∈Vx 0≤k≤q(n) c1,…,ck k f(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,v∈Vx 0≤k≤q(n) f(x,u)=v n ) 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,…,dk k g(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)≠v∈Vx 0≤k≤q(n) d1,…,dk k g(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,v∈Vx v≠0p(n) 0≤k≤q(n) g(x,v)=u d 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,…,ck k
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 V′x={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 G′x 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 G′x 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 G′x 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.
quelle