Czy znalezienie świadka może być trudne, nawet jeśli już wiemy, że istnieje?

10

Typowe przykłady problemów trudnych dla NP (klika, 3-SAT, osłona wierzchołków itp.) Są tego typu, w którym nie wiemy, czy odpowiedź brzmi „tak” czy „nie” wcześniej.

Załóżmy, że mamy problem, w którym wiemy, że odpowiedź brzmi tak, a ponadto możemy zweryfikować świadka w czasie wielomianowym.

Czy wtedy zawsze możemy znaleźć świadka w czasie wielomianowym? A może ten „problem wyszukiwania” może być trudny?

complexity-theory np-hard search-problem

— MBA
źródło

1

Jest mało prawdopodobne. Może być trudny do PPAD.

— RB

Nie wiem, czy to zbieg okoliczności, czy nie, ale ten post został opublikowany dzisiaj: ... przypomnienie, że całkowite problemy z wyszukiwaniem nie są kompletne .

— Pål GD

6

TFNP to klasa funkcji wielowartościowych z wartościami, które są weryfikowane wielomianowo i gwarantowane, że istnieją.

W TFNP występuje problem, który jest kompletny pod względem FNP tylko wtedy, gdy NP = co-NP, patrz Twierdzenie 2.1 w:

Nimrod Megiddo i Christos H. Papadimitriou. 1991. O funkcjach całkowitych, twierdzeniach o istnieniu i złożoności obliczeniowej. Teoria Comput. Sci. 81, 2 (kwiecień 1991), 317-324. DOI: 10.1016 / 0304-3975 (91) 90200-L

oraz odniesienia [6] i [11] w. Plik PDF dostępny tutaj .

— Rahul Savani
źródło

2

Nie, nie zawsze możesz znaleźć rozwiązanie w czasie wielomianowym, nawet jeśli wiesz, że istnieje rozwiązanie.

Według Khanna, Linial i Safra [1] (patrz akapit trzeci) już z klasycznej pracy Karpa z 1972 r. Wynika, że barwienie 3-kolorowego grafu 3 kolorami jest trudne dla NP. (Ich praca rozszerza to, aby pokazać, że 4-kolorowe 3-kolorowe grafy są nadal trudne do NP).

Zauważ, że nie jest to sprzeczne z odpowiedzią Rahula Savani . Jest tak, ponieważ dla wszystkich relacji binarnych w FNP musimy być w stanie zweryfikować w czasie wielomianowym, czy jest w relacji. Biorąc pod uwagę, że podejmowanie decyzji, czy trójkolorowy wykres z 3 kolorami jest NP-kompletny, jest mało prawdopodobne, że znalezienie 4-kolorowego wykresu na trójkolorowym grafie jest w FNP, ponieważ nie możemy zweryfikować poprawności wejścia w czasie wielomianowym . Zatem nie ma sprzeczności z wynikiem Megiddo-Papadimitriou. $P$ $P(x,y)$ $x$

[1] Khanna, Sanjeev, Nathan Linial i Shmuel Safra. „O twardości zbliżenia liczby chromatycznej”. Theory and Computing Systems, 1993., Proceedings of the Israel Israel Symposium on the. IEEE, 1993.

— Juho
źródło

1

Jeśli relacja NP jest trudna dla NP w odniesieniu do
niedeterministycznych redukcji Turinga w czasie wielomianowym tylko z odpowiedzią tak , to $\: NP = coNP \;$ .

Dowód:

jeśli relacja NP jest trudna dla NP w odniesieniu do
ko-niedeterministycznych redukcji Turinga w czasie wielomianowym „ tylko odpowiedź” , to:

Niech będzie takie trudne relacja i niech być tak-odpowiedź tylko wspólnie niedeterministyczny wielomian czasie Transformacja Turinga z do . $R$ $M'$ $SAT$ $R$ $\:$ Niech będzie algorytmem coNP podanym przez: $M$
$\;$ Próba przetworzenia domniemanego anty- certyfikatu na certyfikat wewnętrzny i odpowiedzi.
$\;$ Jeśli to się nie powiedzie, wypisz TAK, w przeciwnym razie spróbuj uruchomić na wewnętrznym anty-certyfikacie, podając $M'$
$\;$ taka sama odpowiedź jak poprzednio w przypadku powtarzających się zapytań i przy użyciu odpowiedzi z
$\;$ (zewnętrzny) anty-certyfikat dla wszystkich innych zapytań wyroczni. $\:$ Gdyby byłby bardziej wyraźny $M'$
$\;$ zapytania niż liczba odpowiedzi lub którekolwiek z jego zapytań nie byłyby powiązane przez z $R$
$\;$ odpowiedź na to zapytanie lub da wynik TAK, wyprowadzi TAK, w przeciwnym razie wyśle NIE. Ponieważ bycie wyrocznią dla po prostu nakłada niezależne warunki na odpowiedzi wyroczni, a oznacza redukcję odpowiedzi tylko na tak, pary zapytań i odpowiedzi wytworzone przez i ważny anty-certyfikat mogą zawsze zostać rozszerzone na wyrocznię dla , więc rozwiązuje $M'$ $M$ $M$
$R$
$M'$ $M'$
$R$ $M$ $SAT\hspace{-0.02 in}$ .
A zatem $\: SAT\in coNP \;$ .
Ponieważ jest $SAT$ -hard względem deterministycznych redukcji wielomianowego czasowych $NP$ $\: NP\subseteq coNP \;$ .
Przez symetrię, $\: coNP \subseteq NP \;$ . $\;\;\;\;$ A zatem $\: NP = coNP \;$ .

Dlatego jeśli relacja NP jest trudna dla NP w odniesieniu do
niedeterministycznych redukcji Turinga w czasie wielomianowym $\: NP = coNP \;$ .

1

Nic z tego nie rozumiem. Można zdefiniować „tak odebrania tylko współ-niedeterministyczny wielomian czasie redukcji Turinga”, jest „anty-świadectwo”, a także wyjaśnić, co

jest dokładnie ( „redukcja z R SAT” nie ma sensu do mnie)?

M^{'}

$M'$

— Sasho Nikolov

„Tylko nie-deterministyczna redukcja Turinga w czasie wielomianowym” jest maszyną wyroczni coNP , której wyrocznią jest to, do czego służy redukcja, tak że nigdy nie będzie pytała wyroczni na wejściu, dla którego nie ma wielomianu ciąg że zapytanie jest związana przez

.

R

$R$

$\:$ (nieprzerwany ...)

$\;\;\;\;$

(... nieprzerwany)

$\:$ Anty-certyfikat to odpowiednik certyfikatu , z TAK i NIE zamienionymi.

$\:$

to redukcja wymieniona w zdaniu, które wprowadziło

.

M^{'}

$M'$

M^{'}

$M'$

$\:$ (Naprawiłem literówkę na końcu tego zdania.)

$\;\;\;\;$

1

$T$ $p$ $\langle x, 1^n \rangle$ $y \in \{0,1\}^{p(n)}$ $T(x,y,1^n)$ $y$ $x$

Jedno pytanie może zatem dotyczyć tego, czy algorytm wielomianu czasu dla „WYLICZENIA Y” implikuje $P = NP$

W takim przypadku załóżmy, że możesz rozwiązać (powiedzmy) 3SAT w czasie wielomianowym przy stałej liczbie wywołań wyroczni, która rozwiązuje „OBLICZ Y”, tj. Pewien algorytm którym iff jest zadowalający, przeciwnym razie. Odwróć bit wyjściowy, aby uzyskać , algorytm, w którym iff jest zadowalające, a jeśli jest niezadowalające. $A$ $A(\phi) = 1$ $\phi$ $A(\phi)=0$ $\bar{A}$ $\bar{A}(\phi) = 0$ $\phi$ $\bar{A}(\phi) = 1$ $\phi$

$\bar{A}$ $y$ $T$ $NP = coNP$

$NP = coNP$ $NP$ $k$ $NP$

— Joe Bebel
źródło