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

17

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 z NP-pełnej problemem jest to, że roztwór do ? $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.

— Mark C.
źródło

Zaznacz, jeśli cstheory.stackexchange.com/questions/1639/… odpowiada na twoje pytanie, daj mi znać, a my możemy oznaczyć to jako duplikat. Pytam, ponieważ twoje pytanie wydaje się dość otwarte i być może odpowiedzi na nie mogą pomóc

— Suresh Venkat

Ach, tak, wydaje się, że to odpowiada. Najwyraźniej szukałem „Kolejnego rozwiązania problemu”. Dziękuję Ci!

— Mark C.

1

Odpowiedź Tsuyoshi wydaje się dość odmienna od pozostałych, więc nie jestem pewien, czy zamknięcie tego pytania ma sens. Może Mark, możesz dodać notatkę do pytania przekierowującego czytelników do drugiego pytania (które jest specyficzne dla SAT)?

— Suresh Venkat,

15

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.

— Tsuyoshi Ito
źródło

1

Znam kogoś, kto uważa to za możliwy kierunek pracy doktorskiej, i rozmawialiśmy o tym krótko, choć nic nie wiem o tym obszarze. Nie wydaje się, aby od czasu, gdy zacytowałeś, wiele powtórzeń, choć być może moje umiejętności wyszukiwania są słabe. Czy znasz jakieś ważne dokumenty od 2003 roku?

— Aaron Sterling,

3

@Aaron: Istnieją inne problemy, które są kompletne pod względem FNP przy zmniejszaniu ASP. Jest też kilka artykułów na ten temat autorstwa Takayuki i innych (w tym jedna, w której jestem współautorką :)), a Takayuki napisał pracę doktorską na ten temat. Jednym z późniejszych ulepszeń jest sformułowanie oparte na problemach z obietnicą, które staje się niezbędne, szczególnie gdy mamy do czynienia z kompletnością PSPACE i kompletnością EXP ASP. Niestety żaden z dokumentów nie wydaje się być dostępny za darmo (czuję się głupio, ale nawet nie mam dostępu do własnego papieru za zaporą). Możesz się z nim skontaktować.

— Tsuyoshi Ito,

2

+1 za świetną odpowiedź i za „nawet ja nie mogę uzyskać dostępu do własnego papieru za zaporą”, hehe

— Daniel Apon

7

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.

— Shiva Kintali
źródło

NAE-SAT również. zawsze ma parzystą liczbę rozwiązań.

— Suresh Venkat,

Zgodnie z powyższą dychotomią, kolejny NAE-SAT jest rozwiązany wielomianowo (jak stwierdzono w artykule).

— Mohammad Al-Turkistany,

Pewnie. ale dla NAE-SAT jest to o wiele łatwiejsze: weź dane zadanie i odwróć je. czas liniowy! :)

— Suresh Venkat,

7

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) o $\phi$ $m$ $\phi$

Pytanie: Czy istnieje inne zadowalające przypisanie inne niż ? $\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 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) -Complete i unikalnych SAT (S) -hard. $S$ $S$ $NP$ $coNP$

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

Każda relacja w jest komplementarna. $S$

Każda relacja w to Horn. $S$

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

Każda relacja w jest afiniczna. $S$

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

— Mohammad Al-Turkistany
źródło

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\}$ spełnia warunek 1, a zatem ma co najmniej dwa wyraźnie przydzielone zadowalające zadania.

— Emil Jeřábek wspiera Monikę

S

$S$

1

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?

— Mohammad Al-Turkistany
źródło