Komplexität der Suche nach einer zweiten Lösung bei korrekter Lösung eines NP-vollständigen Problems

17

Ich möchte herausfinden, ob es allgemeine Ergebnisse oder Beispiele zur NP-Vollständigkeit des Problems gibt, eine zweite Lösung für ein NP-vollständiges Problem zu finden. Genauer gesagt interessieren mich Probleme in folgender Form:

Gibt es bei einer gegebenen Lösung für eine Instanz eines NP-vollständigen Problems eine Lösung für ? $S$ $I$ $S' \neq S$ $I$

Beliebige Beispiele für Probleme dieser Art, sowohl NP-vollständige als auch nicht, oder allgemeine Arbeiten oder sogar ein Problem, wie es genannt wird (damit ich meine eigene Suche durchführen kann), wären willkommen.

Eine andere Frage befasst sich speziell mit diesem Thema im Zusammenhang mit SAT.

Ich hoffe, ich frage nicht wirklich etwas Grundlegendes. Es scheint in Garey und Johnson keine Beispiele für solche Dinge zu geben.

Vielen Dank
Mark C.

cc.complexity-theory reference-request np-hardness unique-solution Mark C.
quelle

Markieren Sie , wenn cstheory.stackexchange.com/questions/1639/… Ihre Frage beantwortet, lassen Sie es mich wissen, und wir können dies als Duplikat markieren. Ich frage, weil Ihre Frage offen zu sein scheint und vielleicht die Antworten dort helfen könnten

Suresh Venkat

Ah ja, es scheint zu antworten. Klar, "Another Solution Problem" ist das, wonach ich gesucht habe. Vielen Dank!

Mark C.

1

Die Antwort von Tsuyoshi scheint sich ziemlich von den anderen zu unterscheiden, daher bin ich mir nicht sicher, ob es Sinn macht, diese Frage zu schließen. Vielleicht Mark, könnten Sie der Frage, die die Leser zu der anderen Frage weiterleitet, einen Hinweis hinzufügen (die SAT-spezifisch ist)?

Suresh Venkat

15

Die Frage scheint gelöst zu sein, während ich diese Antwort geschrieben habe, aber ich kann sie trotzdem posten.

Yato und Seta [YS03] (beide sind meine Kollegen, als ich Student war) schlagen einen allgemeinen Rahmen vor, um die NP-Vollständigkeit dieser Art von Problemen zu beweisen, wobei sie als andere Lösungsprobleme oder ASPs bezeichnet werden, und um die NP-Vollständigkeit von zu beweisen die ASPs vieler Rätsel. Sie betrachten einen eingeschränkten Begriff von Verringerungen zwischen Beziehungsproblemen, die als ASP-Verringerungen bezeichnet werden, und zeigen, dass die NP-Härte von ASPs unter ASP-Verringerungen erhalten bleibt und dass viele bekannte Verringerungen tatsächlich als ASP-Verringerungen zwischen natürlichen Beziehungsproblemen angesehen oder in diese umgewandelt werden können.

[YS03] Takayuki Yato und Takahiro Seta. Komplexität und Vollständigkeit der Suche nach einer anderen Lösung und deren Anwendung auf Rätsel. IEICE-Transaktionen zu Grundlagen der Elektronik, Kommunikation und Informatik , E86-A (5): 1052–1060, Mai 2003.

Tsuyoshi Ito
quelle

1

Ich kenne jemanden, der dies als mögliche Richtung für eine Doktorarbeit betrachtet, und wir haben kurz darüber gesprochen, obwohl ich nichts über das Gebiet weiß. Es scheint nicht so, als gäbe es seit dem von Ihnen zitierten Artikel viel Follow-up, obwohl meine Suchfähigkeiten vielleicht schwach sind. Kennen Sie wichtige Veröffentlichungen seit 2003?

Aaron Sterling

3

@ Aaron: Es gibt andere Probleme, bei denen sich gezeigt hat, dass sie unter ASP-Reduzierbarkeit FNP-vollständig sind. Es gibt auch mehrere Artikel zu diesem Thema von Takayuki und anderen (einschließlich eines Artikels, in dem ich Mitautor bin :)), und Takayuki hat eine Doktorarbeit zu diesem Thema geschrieben. Eine der späteren Verbesserungen ist eine Formulierung, die auf Versprechungsproblemen basiert. Dies ist besonders dann wichtig, wenn es um die PSPACE-Vollständigkeit und EXP-Vollständigkeit von ASPs geht. Leider scheint keines der Papiere frei verfügbar zu sein (ich fühle mich dumm, aber selbst ich kann nicht auf mein eigenes Papier hinter der Paywall zugreifen). Vielleicht möchten Sie ihn kontaktieren.

Tsuyoshi Ito

2

+1 für eine großartige Antwort und für "Selbst ich kann nicht auf mein eigenes Papier hinter der Paywall zugreifen", hehe

Daniel Apon

7

Bei gegebener Hamilton-Schaltung in einer Grafik finden Sie eine andere Hamilton-Schaltung. Dies ist FNP-vollständig. Interessanterweise gibt es Probleme, bei denen die "andere Lösung" durch ein Paritätsargument garantiert ist. Zum Beispiel: Suchen Sie bei einer Hamilton-Schaltung in einem Diagramm mit drei Regeln eine zweite Hamilton-Schaltung. Beachten Sie, dass das Auffinden eines Hamilton-Schaltkreises in einem 3-regulären Graphen NP-vollständig ist. Das Finden des zweiten ist in PPA, vorausgesetzt, das Diagramm ist hamiltonisch.

Weitere Details finden Sie in meinem Blogbeitrag .

Shiva Kintali
quelle

NAE-SAT auch. es gibt immer eine gerade Anzahl von Lösungen.

Suresh Venkat

Gemäß der obigen Dichotomie ist ein anderes NAE-SAT polynomiell lösbar (wie in der Veröffentlichung angegeben).

Mohammad Al-Turkistany

Sicher. Aber für NAE-SAT ist es viel einfacher: Nehmen Sie die vorgegebene Aufgabe an und drehen Sie sie um. lineare Zeit! :)

Suresh Venkat

7

Laurent Juban hat im Dichotomiesatz für das generalisierte Unique Satisability Problem einen Dichotomiesatz für ein anderes SAT bewiesen, das wie folgt definiert ist:

$\phi$ $m$ $\phi$

$\phi$ $m$

Hier ein Auszug aus der Arbeit mit dem Dichotomiesatz:

$S$ $S$ $NP$ $coNP$

$S$

$S$

$S$

$S$

$S$

$S$

Mohammad Al-Turkistany
quelle

S = {⊥, x \lor y \lor \neg z, x \lor \neg y \lor \neg z}

$S=\{\bot,x\lor y\lor\neg z,x\lor\neg y\lor\neg z\}$

S

$S$

S

$S$

S

$S$

⊥

$\bot$

S^{'}

$S'$

S^{'} = S ∖ {⊥}

$S'=S\setminus\{\bot\}$ Befolgung der Bedingung 1, daher hat es mindestens zwei explizit gegebene befriedigende Aufgaben.

Emil Jeřábek unterstützt Monica

S

$S$

1

Hier ist ein weiteres Beispiel aus diesem Artikel : DIE RECHNUNGSKOMPLEXITÄT, KRITISCHE SETS ZU ERKENNEN :

$NP$

$G$

Frage : Gibt es eine andere Kantenpartition als die angegebene?

$NP$

$P$ $P$

Frage : Gibt es eine weitere Vervollständigung eines lateinischen Quadrats?

Mohammad Al-Turkistany
quelle

Komplexität der Suche nach einer zweiten Lösung bei korrekter Lösung eines NP-vollständigen Problems

Antworten: