Was ist falsch an diesem uniform ?

Folgendes wird nicht als wahr angesehen:

$\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

Können Sie mir helfen zu sehen, wo das Argument zusammenbricht?

Das Problem der gerichteten Erreichbarkeit ist für . Ich behaupte, dass es in -uniform . $\mathsf{L}$ $\mathsf{L}$ $\mathsf{NC^1}$

Das Problem der gerichteten Erreichbarkeit über Konfigurationsgraphen der deterministischen Log-Space-Turing-Maschine ist für . $\mathsf{L}$

Das Problem der gerichteten Erreichbarkeit befindet sich in : $\mathsf{MSO}_2$

gegeben und , lassen die freie repräsentieren Variable für die Kanten im Weg. Wir müssen , um sicherzustellen , daß einen gerichteten Weg von enthält zu , die durch die Überprüfung durchgeführt werden kann , dass die in Grad und Ausgangsgrad (in ) von jedem Scheitelpunkt trifft auf einer Kante in ist mit Ausnahme von und der haben In-Grad, Out-Grad = bzw. . $s$ $t$ $P$ $\mathsf{MSO}$ $P$ $s$ $t$ $P$ $P$ $1$ $s$ $t$ $0,1$ $1,0$

Jeder Wald ist ein Diagramm der Baumbreite . Insbesondere ist der Konfigurationsgraph einer deterministischen Log-Space-Turing-Maschine eine Struktur mit begrenzter Baumbreite. $1$

Aus den Logspace-Versionen von Elberfeld, Jakoby und Tantau der Theoreme von Bodlaender und Courcelle :

$\mathsf{MSO}$ Formel über begrenzte kann im Protokollbereich ausgewertet werden.

Der Beweis so: Für eine gegebene Strukturgröße , eine Grenze für die der Strukturen und eine -Formel mit Vokabular , Konstrukt (in ) Konstrukt , das eine Schaltung . $n$ $w$ $\mathsf{MSO}$ $\varphi$ $\tau$ $\mathsf{L}$ $\#\mathsf{NC}^1$ $C$

Die Schaltung eine Struktur gegeben der Größe und Baumbreite höchstens , zählt die Anzahl der „befriedigend“ Zuordnungen von auf . $C$ $M$ $n$ $w$ $\varphi$ $M$

(Das Histogramm, in dem die Anzahl der Zuordnungen zu den freien Variablen zweiter Ordnung in tabellarisch aufgeführt ist, wird anhand der Größe der von den Variablen übernommenen parametrisiert.) $\varphi$

Ich denke, die Schaltung hängt nur vom Vokabular , der Baumbreitengrenze und der Größe der Struktur . $C$ $\tau$ $d$ $n$

Der Beweis erfolgt durch Auswertung der Schaltung in aber wir brauchen diesen Teil nicht. $\#\mathsf{NC}^1 \subseteq \mathsf{L}$

Für uns genügt es , dass aus zu beobachten Nichtdeterministische Berechnung $\mathsf{NC^1}$ von Caussinus-Mackenzie-Therien-Vollmer:

Jeder Schaltkreis kann so interpretiert werden, dass er die Anzahl der eines Schaltkreises zählt. $\#\mathsf{NC}^1$ $\mathsf{NC}^1$

Somit gibt die entsprechende Schaltung wenn die Eingabestruktur die Formel erfüllt . $1$ $\mathsf{MSO}$

Aus dem Obigen geht hervor, dass sich der Log-Space mindestens in Logspace-Uniform $\mathsf{NC}^1$

cc.complexity-theory graph-algorithms complexity-classes descriptive-complexity finite-model-theory SamiD
quelle

Ihr MSO-Erreichbarkeitsargument ist nicht ganz richtig: Es funktioniert nur, wenn der durch die Eckpunkte induzierte Teilgraph ein gerichteter Pfad ist, was im Allgemeinen nicht der Fall ist (ein triviales Gegenbeispiel ist ein symmetrisches Paar gerichteter Kanten). Der richtige Weg, um die Erreichbarkeit in MSO zu erreichen, besteht darin, zu behaupten, dass jede Scheitelpunktmenge, die enthält und unter der Kantenbeziehung geschlossen ist, auch .

P

$P$

s

$s$

t

$t$

David Richerby

@SamiD Ich habe das kleinste Gegenbeispiel gegeben, das zufällig ein symmetrischer Graph ist. Aber der 3-Vertex-Graph mit den gerichteten Kanten , , funktioniert genauso gut: Der eindeutige gerichtete Pfad von nach ist aber die Menge erfüllt Ihre Formel nicht, weil in dem durch induzierten Teilgraphen (der der gesamte Graph ist) keinen Nullpunkt und keinen Nullpunkt hat.

a \to b

$a\to b$

b \to c

$b\to c$

c \to a

$c\to a$

a

$a$

c

$c$

a b c

$abc$

{a, b, c}

$\{a,b,c\}$

{a, b, c}

$\{a,b,c\}$

a

$a$

c

$c$

David Richerby

@ David Point gut gemacht - meine ursprüngliche Formulierung war fehlerhaft - ich hoffe, diese ist in Ordnung: Ich betrachte eine Reihe von Kanten anstelle von Scheitelpunkten und schaue auf den Grad der Scheitelpunkte zu diesen Kanten - sie müssen dieselben sein wie zuvor. Danke für das Beispiel.

SamiD

@Kaveh Danke für die Änderungen - sie machen die Frage lesbarer. Ich habe das von Ihnen angesprochene Problem geklärt. Nach meinem Verständnis erstellt EJT eine logarithmische Arithmetikschaltung in L, und dann fällt das Problem aufgrund des CMTV-Containments # NC1 \ subseteq L in L ab. Wir hören jedoch an dem Punkt auf, an dem die Schaltung erstellt und syntaktisch erstellt wird Wandle es in eine NC ^ 1-Schaltung um. Die Konvertierung usw. kann problemlos durchgeführt werden. Ich habe NC ^ 1 / poly in L-einheitliches NC ^ 1 konvertiert, auch weil es genauer ist.

SamiD

@Kaveh: 1. Wenn Sie jede von Schaltung in und in ändern , wird eine Schaltung so dass die Anzahl der Beweisbäume von .

+

$+$

# N C^{1}

$\#NC^1$

C

$C$

\lor

$\vee$

*

$*$

\land

$\wedge$

N C^{1}

$NC^1$

C^{'}

$C'$

C

$C$

C^{'}

$C'$

SamiD

Was ist falsch an diesem uniform ?

Antworten: