Złożoność znalezienia drugiego rozwiązania przy poprawnym rozwiązaniu problemu NP-zupełnego

Chcę dowiedzieć się, czy istnieją jakieś ogólne wyniki lub przykłady dotyczące kompletności NP problemu znalezienia drugiego rozwiązania problemu NP-zupełnego. Dokładniej, jestem zainteresowany wszelkimi problemami następującej formy:

Biorąc pod uwagę rozwiązanie na przykład I z NP-pełnej problemem jest to, że roztwór S ' ≠ S do I ?$S$$I$$S' \neq S$$I$

Docenione zostaną wszelkie przykłady tego rodzaju problemów, zarówno NP-zupełne, jak i nie, lub ogólna praca, a nawet coś, co nazywa się tego rodzaju problemem (dzięki czemu mogę właściwie przeprowadzić własne wyszukiwanie).

Kolejne pytanie dotyczy tego problemu, szczególnie w odniesieniu do SAT.

Mam nadzieję, że nie pytam o coś naprawdę podstawowego; wydaje się, że w Garey i Johnsonie nie ma takich przykładów.

Dzięki
Mark C.

Pytanie wydaje się być rozwiązane, kiedy pisałem tę odpowiedź, ale mimo to pozwólcie, że opublikuję swoją odpowiedź.

Yato i Seta [YS03] (obaj są moimi kolegami, gdy byłem studentem) proponują ogólne ramy, aby udowodnić kompletność NP tego rodzaju problemów, gdzie są one nazywane Innymi Problemami Rozwiązania lub ASP i udowodnić kompletność NP ASP wielu zagadek. Rozważają ograniczone pojęcie redukcji między problemami relacji zwanymi redukcjami ASP i pokazują, że twardość NP ASP jest zachowana w ramach redukcji ASP i pokazują, że wiele znanych redukcji można faktycznie postrzegać lub modyfikować do redukcji ASP między naturalnymi problemami relacji.

[YS03] Takayuki Yato i Takahiro Seta. Złożoność i kompletność znalezienia innego rozwiązania i jego zastosowania do zagadek. Transakcje IEICE dotyczące podstaw elektroniki, komunikacji i informatyki , E86-A (5): 1052–1060, maj 2003 r.

Biorąc pod uwagę obwód Hamiltona na wykresie, znajdź kolejny obwód Hamiltona. To jest FNP-complete. Co ciekawe, istnieją problemy, w których „inne rozwiązanie” jest gwarantowane przez argument parzystości. Na przykład: Biorąc pod uwagę obwód Hamiltona na 3-regularnym wykresie, znajdź drugi obwód Hamiltona. Zauważ, że znalezienie obwodu hamiltonowskiego na 3-regularnym wykresie jest NP-zakończone. Znalezienie drugiego, biorąc pod uwagę, że wykres jest hamiltonowski, znajduje się w PPA.

Zobacz mój post na blogu, aby uzyskać więcej informacji.

Laurent Juban w twierdzeniu o dychotomii uogólnionego unikalnego problemu satysfakcji udowodnił twierdzenie o dychotomii dla innego SAT zdefiniowanego jako:

Wejście: Wzór zdaniową i spełniającą zadanie (modelu) m o $\phi$$m$$\phi$

Pytanie: Czy istnieje inne zadowalające przypisanie inne niż m ?$\phi$$m$

Oto fragment artykułu z twierdzeniem o dychotomii:

Twierdzenie 1 (Twierdzenie o dychotomii). Niech będzie skończonym zestawem relacji logicznych. Jeśli S spełnia jeden z poniższych warunków (1) do (6), KOLEJNE SAT (S) i UNIKALNE SAT (S) są rozwiązywalne w czasie wielomianowym. W przeciwnym wypadku, kolejny SAT (S) N P -Complete i unikalnych SAT (S) C O N P -hard.$S$$S$$NP$$coNP$

1. Każda relacja w jest zerowa i 1 ważna.$S$

2. Każda relacja w jest komplementarna.$S$

3. Każda relacja w to Horn.$S$

4. Każda relacja w jest anty-Horn.$S$

5. Każda relacja w jest afiniczna.$S$

6. Każda relacja w to 2SAT.$S$

Oto kolejny przykład z tego artykułu KOMPUTACYJNA KOMPLEKSOWOŚĆ UZNAWANIA ZESTAWÓW KRYTYCZNYCH :

$NP$

$G$

Pytanie : Czy istnieje inna partycja brzegowa inna niż podana?

$NP$

$P$$P$

Pytanie : Czy istnieje inne uzupełnienie łacińskiego kwadratu?