Wie komplex ist das Universalitätsproblem für eine NFA, die von allen Staaten akzeptiert wird?

Es ist bekannt, dass das Universalitätsproblem für NFA (Entscheidung, ob ) vollständig ist. Was ist jedoch, wenn bekannt ist, dass jeder Staat der NFA akzeptiert? Es scheint mir , dass das Problem bei den meisten in ist - , als Gegenbeispiel (anders als im Fall eines allgemeinen NFA) ist Polynom (auch linear) in der Größe des Eingangs (die Anzahl der Zustände). Was ist die Komplexität dieses Problems? $L(A)=\Sigma^*$ $PSPACE$ $co$ $NP$

complexity-theory regular-languages finite-automata pron
quelle

Sofern mein Beweis kein Problem enthält, ist es sehr unwahrscheinlich, dass Ihr Problem Co-NP ist, da dies bedeuten würde, dass Co-NP = PSPACE. Da ein Gegenbeispiel (dh ein abgelehntes Wort) tatsächlich in seiner Größe im Zeitpolynom überprüft werden könnte, würde ich sagen, dass Ihr Beweis, dass es immer ein Gegenbeispiel für die Polynomgröße gibt, ein Problem enthalten muss. Könnten Sie bitte erklären, wie Sie ein solches Gegenbeispiel für die Polynomgröße finden würden? Das einzige, woran ich denken konnte, war die Suche nach einem kürzesten Weg zu einem Zustand, in dem die Übergangsfunktion nicht vollständig ist, aber es könnte einen anderen Weg geben, der funktioniert ...

xavierm02

Es ist nicht wahr, dass das kürzeste Gegenbeispiel eine Polynomgröße hat. Sie sich eine NFA vor, deren Anfangszustand mit Zyklen der Längen . Sie können dafür sorgen, dass das Wort nur dann nicht akzeptiert wird, wenn ungerade ist und ein Vielfaches von . Wenn Sie als erste Primzahlen auswählen , erhalten Sie eine NFA mit -Zuständen, in denen das kürzeste abgelehnte Wort die Länge .

2, p_{1}, \dots, p_{m}

$2,p_1,\ldots,p_m$

1^{n} 0

$1^n0$

n

$n$

p_{1}, \dots, p_{m}

$p_1,\ldots,p_m$

p_{i}

$p_i$

m + 1

$m+1$

O (m^{2} \log m)

$O(m^2\log m)$

e^{(1 + o (1)) m \log m}

$e^{(1+o(1))m\log m}$

Yuval Filmus

Eine einfache Reduzierung von SAT zeigt, dass das Problem tatsächlich coNP-schwer ist. Die NFA verzweigt sich gemäß den Klauseln in Teile. Jeder Teil prüft, ob die Eingabe, die aus einer Zuweisung gefolgt von , die Klausel erfüllt, und bleibt in diesem Fall am endgültigen . Diese NFA ist nicht universell, wenn die SAT-Instanz erfüllt werden kann.

$

$\$$

$

$\$$

Yuval Filmus

@YuvalFilmus Sie haben Recht mit dem Gegenbeispiel, aber wie sich herausstellt, habe ich das Problem falsch angegeben. Ich weiß, dass keine Wörter mit aufeinanderfolgenden sich wiederholenden Buchstaben hat, und ich suche nach Universalität in Bezug auf alle Wörter ohne aufeinanderfolgende sich wiederholende Buchstaben. Gibt es auch in diesem Fall ein exponentielles Gegenbeispiel?

L (A)

$L(A)$

Pron

@ YuvalFilmus Außerdem ist das Alphabet nicht größer als die Anzahl der Staaten + 1.

Pron

Antworten:

Ihr Problem ist PSPACE-vollständig. Ich beweise, dass es PSPACE-schwer ist, indem ich die Universalität von NFAs auf die Universalität von NFAs reduziere, wobei alle Staaten dies akzeptieren.

Sei eine NFA. Fügen Sie einen neuen Endzustand und fügen Sie für jeden akzeptierenden Zustand einen Übergang wobei ein neuer Buchstabe ist. für jeden Buchstaben auch einen Übergang . Und dann alle Staaten akzeptieren lassen. Der neue Automat akzeptiert für einige . $A$ $q_\$$ $q$ $q\overset{\$}{\to}q_\$$ $\$$ $a\in \Sigma\sqcup \{\$\}$ $q_\$\overset{a}{\to}q_\$$ $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup L'$ $L'\subseteq \Sigma^*$

Fügen Sie nun einen Automaten (mit allen endgültigen Zuständen) hinzu, der die Sprache (dh die Sprache der Wörter, die nicht enthalten ) parallel erkennt . Der neue Automat erkennt . $\Sigma ^*$ $\$$ $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup (L' \cup \Sigma ^*)=L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*$

nun, dass wir wenn . Das heißt, der von mir beschriebene Prozess ist eine Reduktion von der Universalität einer NFA auf die Universalität einer NFA, wobei alle Staaten dies akzeptieren. Da die Reduktion polynomisch ist, ist Ihr Problem PSPACE-schwer. $L(A)=\Sigma^*$ $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*=(\Sigma\sqcup\{\$\})^*$

xavierm02
quelle

Wie erstellt man eine NFA für deren alle akzeptieren?

Σ^{*} ∖ Σ^{*} $

$\Sigma^* \setminus \Sigma^*\$$

Yuval Filmus

Vielen Dank, das ist eine schöne Reduzierung und beantwortet in der Tat meine Frage. Ich hatte jedoch eine andere, komplexere Frage im Kopf, von der ich dachte, ich könnte sie auf diese reduzieren, und das exponentielle Gegenbeispiel von @YuvalFilmus ließ mich erkennen, dass meine eigene Reduktion fehlerhaft war, und ich hätte die Einschränkung hinzufügen sollen, dass enthält keine Wörter mit wiederholten Buchstaben, und ich überprüfe, ob diese Wörter "universell" sind.

L (A)

$L(A)$

Pron

@pron Was meinst du mit "Wort mit wiederholten Buchstaben"? Dass oder dass ?

u = v_{1} a a v_{2}

$u=v_1aav_2$

u = v_{1} a v_{2} a v_{3}

$u=v_1av_2av_3$

Xavierm02

@ xavierm02 Der erste, dh keine aufeinanderfolgenden wiederholten Buchstaben. Gibt es auch in diesem Fall ein exponentielles Gegenbeispiel?

Pron

@ xavierm02 Auch das Alphabet ist nicht größer als die Anzahl der Staaten + 1.

pron