Czy „Drugi X jest kompletny NP” oznacza, że „X jest kompletny NP”?

Problem „drugiego ” to problem decydowania o istnieniu innego rozwiązania innego niż niektóre dane rozwiązanie problemu. $X$

W przypadku niektórych uzupełnieniem druga wersja rozwiązania to zupełne (decydujące o istnieniu innego rozwiązania dla częściowego problemu częściowego uzupełnienia kwadratu łacińskiego), podczas gdy dla innych jest albo trywialne (Drugi NAE SAT), albo nie może być uzupełnieniem (Drugi cykl hamiltonowski na wykresach sześciennych) przy powszechnie uznawanej hipotezie złożoności. Interesuje mnie odwrotny kierunek. $NP$ $NP$ $NP$

Zakładamy naturalną problemu gdzie istnieje naturalny wydajny weryfikator, który sprawdza naturalnym interesująca relacja , gdzie jest instancją wejściowy i jest krótkie świadectwo członkostwa w . Wszyscy świadkowie są nie do odróżnienia od weryfikatora. Ważność świadków należy ustalić, uruchamiając naturalnego weryfikatora i nie ma ona żadnej wiedzy o żadnym prawidłowym świadku (oba przykłady w komentarzach są rozwiązaniami z definicji). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

Czy „Drugi jest kompletny NP” oznacza, że „ jest kompletny NP” dla wszystkich „naturalnych” problemów ? $X$ $X$ $X$

Innymi słowy, czy istnieje jakiś „naturalny” problem którym ta implikacja zawodzi? $X$ . Lub równoważnie

Czy istnieje jakiś „naturalny” Problem w i nie wiadomo, -Complete ale jego drugie problemem jest -Complete? $X$ $NP$ $NP$ $X$ $NP$

EDYCJA : Dzięki komentarzom Marzio nie interesują mnie wymyślone kontrprzykłady. Interesują mnie tylko naturalne i interesujące kontrprzykłady dla problemów z uzupełnieniem NP podobnych do powyższych. Akceptowalna odpowiedź albo potwierdzenie powyższego pośrednio lub Kontrprzykład „Drugi X problem”, który jest zdefiniowany przez naturalne, interesujące i znanego problemu . $X$ $NP$ $X$

EDIT 2 : Dzięki owocnej dyskusji z Davidem Richerby, mam pytanie do edycji naciskiem, że moje zainteresowanie jest tylko w naturalnym problemów . $X$

Edycja 3 , uzasadnienie: Po pierwsze, obecność takiego pośrednio można uprościć -completeness dowody wielu problemów. Po drugie, istnienie pośrednio łączy złożoność decydując wyjątkowość rozwiązania problemu decydując istnienie rozwiązanie dla problemów. $NP$ $NP$ $NP$

cc.complexity-theory unique-solution

— Mohammad Al-Turkistany
źródło

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

— Bjørn Kjos-Hanssen

Wydaje się, że twoje EDIT 3 i EDIT 1 nie są w jednej linii. Jeśli chcesz, aby był to ogólny wynik, przydatny do uproszczenia dowodów kompletności NP, nie możesz także powiedzieć, że chcesz tylko „nieskomplikowanych” kontrprzykładów. Przydałaby się również definicja „naturalna / interesująca”, która nie była oparta na osobistej opinii.

— Chris Jefferson

Odpowiedzi:

Nie,

Rozważ problem „Znajdź podzbiór zbioru liczb całkowitych S, który sumuje się na 0”.

Ten problem jest trywialny, ponieważ można zwrócić pusty zestaw.

Jednak znalezienie drugiego rozwiązania po zwróceniu pustego zestawu jest dobrze znanym problemem sumy podzbiorów, o którym wiadomo, że jest NP-zupełny.

— Chris Jefferson
źródło

Jeśli nie możesz zdefiniować „nienaturalnego” problemu, nie ma to znaczenia. Ludzie definiują setki wariantów problemów, takich jak suma podzbiorów i SAT.

— Chris Jefferson

@Mohammad: Oto kolejny kontrprzykład; Pozostawiam wam decyzję, czy jest to naturalne, czy nie: gra bimatrix zawsze ma co najmniej jedną równowagę Nasha i trudno jest zdecydować, czy gra bimatrix ma więcej niż jedną równowagę Nasha [Gilboa i Zemel, GEB 1989] . Konstrukcja przyjmuje wzór SAT i tworzy grę z pewną równowagą Nasha o znanej formie, która zawsze istnieje, tak że gra ma drugą równowagę, jeśli wzór f jest zadowalający.

— Rahul Savani

Oto inny kontrprzykład, jednowymiarowa wersja lematu Spernera, podobna duchem do tej, którą zapewnia Rahul. Biorąc pod uwagę logiczny obwód obliczania funkcji

(wkład jest zaopatrzony w podwójną) z obiecując

, a

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

, znajdź liczbę

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$ taka, że

, a

. Taka liczba zawsze istnieje i jest łatwa do znalezienia poprzez wyszukiwanie binarne, ale trudno jest zdecydować, czy istnieje więcej niż jedna taka pozycja, w której ma to miejsce.

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

— Robert Andrews,

NP complete nie oznacza, że wszystkie instancje są trudne, tylko niektóre są. Istnieje wiele trywialnych przypadków sumy podzbiorów (wszystkie problemy, które zawierają na przykład 1 i - 1) i wiele łatwych problemów SAT (na przykład 2 SAT), ale SAT jako całość jest nadal NP-kompletny.

— Chris Jefferson

Odpowiedź musi być podzbiorem zbioru liczb całkowitych S. {} jest podzbiorem S, ponieważ pusty zbiór jest podzbiorem wszystkich zbiorów. {ϕ} nie jest podzbiorem S, ponieważ S nie zawiera ϕ

— Chris Jefferson

Odpowiedź brzmi: tak (jeśli zamiast redukcji Karp stosuje się redukcję ASP). Redukcja ASP wymaga obliczenia wielomianowego czasu obliczeniowego między zestawami rozwiązań dwóch problemów. Zapewnia to oszczędne zmniejszenie problemów związanych z kompletowaniem ASP. Yato i Seta twierdzą, że $ASP$ -completeness oznaczać -completeness (strona 2, drugi akapit). Innym problemem rozwiązania (ASP) jest dokładnie to, co nazywam problemem Second X. $NP$

Oded Goldreich stwierdza fakt, że „wszystkie znane redukcje wśród naturalnych $NP$ -Complete problemy są zarówno oszczędne lub mogą być łatwo modyfikowane, aby być tak”. ( Złożoność obliczeniowa: perspektywa koncepcyjna Oded Goldreich ). Dlatego prawdopodobne jest, że redukcje Karp między naturalnymi problemami NP-zupełnymi mogą być modyfikowane, aby były redukcjami ASP.

— Mohammad Al-Turkistany
źródło

Problem polegał na tym, czy kompletność NP drugiego rozwiązania oznacza kompletność NP. To, co pokazują, jest słabsze, wymaga kompletności ASP, ponieważ kompletność NP nie wystarczy, jak wskazano w komentarzach do twojego pytania.

— domotorp

Jeśli ktoś to przeczyta, ta odpowiedź jest błędna. Łatwo jest stworzyć problem, w którym drugie X jest kompletne NP, ale X nie jest kompletne NP. Na przykład (jak omówiono w komentarzach powyżej) problemem znalezienia podzbioru zbioru liczb całkowitych, który sumuje się do 0, jest Drugi X NP-zupełny, ponieważ jest on NP-kompletny, gdy odrzucimy łatwe pierwsze rozwiązanie pustego zestawu .

— Chris Jefferson

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

— Sasho Nikolov

To trochę dziwne, że ktoś zadaje pytanie, odpowiada na nie, a następnie akceptuje je w trakcie dyskusji.

— Chandra Chekuri,

@ MohammadAl-Turkistany Mój komentarz mówił, że twoja odpowiedź wydaje się logiczna i nie odpowiada na twoje własne pytanie. Nie powiedziałem nic o przykładzie Chrisa (który dla mnie wygląda dobrze, ale nie chcę wchodzić w ten argument w komentarzach).

— Sasho Nikolov

Czy „Drugi X jest kompletny NP” oznacza, że ​​„X jest kompletny NP”?

Czy „Drugi X jest kompletny NP” oznacza, że „X jest kompletny NP”?