Beispiele, bei denen die Eindeutigkeit der Lösung das Auffinden erleichtert

37

Die Komplexitätsklasse besteht aus denjenigen -Problemen, die von einer polynomiell zeitlich nicht deterministischen Turing-Maschine entschieden werden können, die höchstens einen akzeptierenden Rechenweg hat. Das heißt, die Lösung ist, wenn überhaupt, in diesem Sinne einzigartig . Es ist höchst unwahrscheinlich, dass alle -Probleme in , da dies nach dem Valiant-Vazirani-Theorem den Zusammenbruch implizieren würde . $\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{UP}$ $\mathsf{P}$ $\mathsf{NP}=\mathsf{RP}$

Auf der anderen Seite, keine ist -Problem bekannt ist, dass -komplette, die diese Anforderung die eindeutige Lösung schlägt vor , noch irgendwie macht sie leichter. $\mathsf{UP}$ $\mathsf{NP}$

Ich suche nach Beispielen, bei denen die Annahme der Eindeutigkeit zu einem schnelleren Algorithmus führt.

Wenn Sie sich zum Beispiel Diagrammprobleme ansehen, kann eine maximale Clique in einem Diagramm schneller gefunden werden (obwohl möglicherweise immer noch in exponentieller Zeit), wenn wir wissen, dass das Diagramm eine eindeutige maximale Clique hat? Wie wäre es mit einer einzigartigen Färbbarkeit, einem einzigartigen Hamilton-Pfad, einer einzigartigen minimalen dominierenden Menge usw.? $k$

Im Allgemeinen können wir für jedes -komplette Problem eine eindeutige Lösungsversion definieren und diese auf verkleinern . Ist bekannt, dass das Hinzufügen der Eindeutigkeitsannahme zu einem schnelleren Algorithmus führt? (Erlaubt, dass es immer noch exponentiell bleibt.) $\mathsf{NP}$ $\mathsf{UP}$

cc.complexity-theory ds.algorithms graph-algorithms complexity-classes unique-solution Andras Farago
quelle

7

Ihr erster Satz enthält die korrekte Definition von UP, aber der Rest Ihrer Verweise auf UP sollte sich eigentlich auf PromiseUP beziehen (einschließlich Valiant-Vazirani). In jedem Fall ist dies eine sehr interessante Frage. Zwei Beispiele: 1) Factoring ist in UP und hat einen Algorithmus schneller als die bekannten für NP-vollständige Probleme (aber Factoring ist auch in coNP und sogar coUP, so ist es nicht so klar , dass die Einzigartigkeit des schnellen Algorithmus zugrunde liegt hier) 2. ) Sodoku ist, wie traditionell definiert, in PromiseUP enthalten, ich kenne jedoch keine Ansätze für Sudoku-Lösungen, die die versprochene Einzigartigkeit nutzen.

Joshua Grochow

9

{1.618}^{n}

$1.618^n$

2^{n}

$2^n$

8

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

n

$n$

22

3-SAT kann ein solches Problem sein. Derzeit ist die beste Obergrenze für Unique 3-SAT exponentiell schneller als für General 3-SAT. (Die Beschleunigung ist exponentiell, obwohl die Verringerung des Exponenten sehr gering ist.) Der Rekordhalter für den einzigartigen Fall ist dieses Papier von Timon Hertli.

$k$ $k \geq 5$ $k$ $k$ $k = 3, 4$ $k$

$k$ $k$ $\delta < 1$ $n$ $k$ $O^*(2^{\delta n})$ $k \geq 3$ $k$ $k$ $k \geq 3, \epsilon > 0$ $k$ $O^*(2^{\epsilon n})$

$O^*$

Andy Drucker
quelle

1

"wahr für Unique 3-SAT"

\mapsto

$\: \mapsto \:$ "wahr für Unique k-SAT"

$\;\;\;\;$

Hallo Ricky, ich sehe kein Problem mit dem, was geschrieben steht. Die letzte Aussage zu Unique 3-SAT findet sich in der Zusammenfassung der Zeitung.

Andy Drucker

k

$k$

$\hspace{1.58 in}$ das würde es nur verwirrend machen.

$\;$

16

Kürzestes 2-Vertex-Problem mit disjunktem Pfad in ungerichteten Graphen, das kürzlich von A. Bjorklund und T. Husfeldt gelöst wurde (ICALP14). Die deterministische Lösung ist jedoch für den Fall der Existenz einer eindeutigen Lösung. Für den Fall, dass es mehr als eine Lösung gibt, wurde gezeigt, dass das Problem zu RP gehört . Wie die Autoren des genannten Papiers wissen, ist im allgemeinen Szenario nicht bekannt, ob das Problem bei P liegt .

Saeed
quelle

3

Danke, es ist sehr interessant. Der allgemeine Fall, in dem die Lösung nicht eindeutig ist, ist auch ein schönes Beispiel für ein natürliches (oder sogar praktisches) Diagrammproblem, das sich jetzt in RP, aber nicht in P.

Andras Farago befindet.

10

Außerhalb der Komplexitätstheorie und der Analyse von Algorithmen bildet die Annahme, dass es nur eine Lösung geben kann, die Grundlage für einige der Standardregeln, die zur Ableitung der Lösung in Sudoku-Rätseln verwendet werden. Diese Regeln beinhalten im Allgemeinen die Suche nach Möglichkeiten, wie Teile des Puzzles zwei oder mehr Lösungen haben können, die nicht mit dem Rest des Puzzles interagieren. Dies kann in der tatsächlichen Lösung nicht passieren. Wenn also ein Muster gefunden wird, das dies zu verursachen droht, muss es beschädigt werden, damit der Löser Einschränkungen für das Erscheinungsbild der tatsächlichen Lösung ableiten kann. Unter http://www.brainbashers.com/sudokuuniquerectangles.asp finden Sie einige Beispiele für Abzugsregeln, die auf der Eindeutigkeit basieren.

David Eppstein
quelle

9

$G$

Die Annahme der Einheitlichkeit bedeutet, dass die Parität der Anzahl der Schinken. Pfade ist das Gleiche, als würde man entscheiden, ob es sich bei dem Graphen um ein Hamilton-Diagramm handelt.

$O(1.619^n)$ $O^*(1.657^n)$ $O(n^22^n)$

RB
quelle

Beispiele, bei denen die Eindeutigkeit der Lösung das Auffinden erleichtert

Antworten: