Intuition für die UP-Klasse

Die UP-Klasse ist als solche definiert :

Die Klasse von Entscheidungsproblemen, die von einer NP-Maschine so gelöst werden können, dass

Wenn die Antwort "Ja" lautet, wird genau ein Berechnungspfad akzeptiert.

Wenn die Antwort "Nein" lautet, werden alle Berechnungspfade abgelehnt.

Ich versuche, eine Intuition für diese Definition zu entwickeln.

Kann man sagen, dass UP-Probleme die Probleme mit einzigartigen Lösungen sind (z. B. Primfaktorisierung)?

Das scheint mir der Wahrheit nahe zu sein; aber ich kann mir nicht helfen zu denken, dass dies bedeuten würde, da UP P enthält und in NP enthalten ist, dass für den Fall, dass P = NPwir das bekommen würden P = UP = NP, alle Probleme NPauch einzigartige Lösungen haben, was scheinbar etwas ist, das nachweislich nicht wahr ist: P != NPvon reductio ad absurdum. Ich hoffe, dass dieser Absatz nicht zu viele Vermutungen und Handbewegungen für Ihren Geschmack enthält.

cc.complexity-theory complexity-classes Valya
quelle

Die Definition von „einzigartiger Lösung“ ist problematisch: Lösung Parity - Spiele zum Beispiel in UP (UP

coUP, in der Tat), aber es kann viele erfolgreichen Strategien sein. Der einzigartige Zeuge ist mehr involviert.

\cap

$\cap$

Shaull

hm, das würde bedeuten, dass es einen Algorithmus für eine nicht deterministische Turing-Maschine gibt, der nicht "nicht deterministisch jede Lösung ausprobiert" (ich dachte, das ist die Idee im Herzen der Äquivalenz der Definitionen von NP für n.-d. und d. Tm), aber etwas Anspruchsvolleres, das immer zu dem einzigartigen Ergebnis von vielen möglichen führt ... Ist das richtig? Gibt es eine andere Möglichkeit, dies zu formulieren, beispielsweise nur mit der Idee eines deterministischen Tm (man kann NP nur damit definieren)?

Valya

Die Intuition eines eindeutigen Zeugen ist korrekt, muss jedoch sorgfältig verwendet werden, da dies nicht bedeutet, dass jeder NTM dafür einen eindeutigen Lauf hat.

Shaull

Ich liebe diese Frage! Ich hatte genau die gleiche Verwirrung, aber ich sah nicht den klugen Weg, diese Verwirrung in einen einfachen Beweis zu übersetzen, dass P! = NP. Gut gemacht!

Vincent

Übrigens wurde Ihre Frage aus Ihrem letzten Kommentar seitdem auf der Wikipedia-Seite für die UP-Klasse beantwortet

Vincent

Antworten:

$\mathsf{NP}$ Eine andere Art von Lösung, die gleich gut funktioniert, ist die Zuweisung einer Ausrichtung zu jeder Kante (Erstellen gerichteter Pfade mit höchstens der erforderlichen Anzahl von Scheitelpunkten). Diese beiden Arten von Lösungen können beide in Polynomzeit überprüft werden, jedoch durch unterschiedliche Algorithmen, und sie haben auch unterschiedliche kombinatorische Eigenschaften. Beispielsweise unterscheidet sich für eine typische Probleminstanz die Anzahl der Scheitelpunktfarbzuweisungen von der Anzahl der Kantenausrichtungen. Viele Untersuchungen zur Beschleunigung exponentieller Algorithmen für Probleme vom Typ NP können dahingehend interpretiert werden, dass eine neue Familie von Lösungen für dasselbe Problem gefunden wird, für die weniger Überprüfungsmöglichkeiten bestehen.

$\mathsf{P}$ $\mathsf{NP}$ $\mathsf{UP}$ $\mathsf{P}\subset\mathsf{UP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}=\mathsf{UP}$ . Es besteht also kein Widerspruch zwischen der Tatsache, dass die Lösung mit leeren Zeichenfolgen eindeutig ist, und der Tatsache, dass eine andere Art von Lösung für dasselbe Problem nicht eindeutig ist.

David Eppstein
quelle

U P = N P

$UP=NP$

[a, b]

$[a,b]$

a, b \sim N^{\frac{1}{4}}

$a,b\sim N^{\frac{1}{4}}$

a < b

$a<b$

Auch hier gehen Sie fälschlicherweise davon aus, dass die Lösung nur der Faktor sein kann, den Sie suchen. Es kann andere Möglichkeiten geben, dasselbe Problem zu lösen (dh eine Ja- oder Nein-Antwort für das gegebene N zu erhalten), die nicht aus einem Faktor bestehen. Und wenn P = NP, erfüllt der leere String die technischen Anforderungen einer NP-Lösung - Sie können ihn in Polynomzeit überprüfen - und ist in der Tat kein Faktor, sondern eine Lösung für dasselbe Problem.

David Eppstein

Diese Antwort ist absolut brillant, da sie uns noch mehr lehrt, als verlangt wird!

Vincent

$\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{NPMV}$ $\mathsf{NP}$

$\mathsf{NPSV}$ $\mathsf{NPMV}$

$\mathsf{NP}$ $\mathsf{NPMV}$ $\mathsf{NPSV}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{UP}$ $\mathsf{NP} = \mathsf{UP}$ $L \in \mathsf{NP}$ $\mathsf{UP}$ $L$ $\mathsf{NP}$ $L$

Joshua Grochow
quelle