Dla jakich problemów w P łatwiej jest zweryfikować wynik niż go znaleźć?

W przypadku (wyszukiwania wersji) problemów z NP zakończonych weryfikacja rozwiązania jest wyraźnie łatwiejsza niż znalezienie, ponieważ weryfikacja może być przeprowadzona w czasie wielomianowym, podczas gdy znalezienie świadka zajmuje (prawdopodobnie) wykładniczy czas.

Jednak w P rozwiązanie można znaleźć również w czasie wielomianowym, więc nie wydaje się oczywiste, kiedy weryfikacja jest szybsza niż znalezienie rozwiązania. W rzeczywistości różne problemy wydają się zachowywać inaczej z tego punktu widzenia. Kilka przykładów:

1. 3SUMA: biorąc pod uwagę liczb wejściowych, znajdź 3 spośród nich, które sumują się do 0. O ile mi wiadomo, najszybszy znany algorytm działa w czasie , a ta kolejność jest przypuszczalna optymalna. Z drugiej strony weryfikacja rozwiązania jest znacznie szybsza, ponieważ wszystko, co musimy zrobić, to po prostu sprawdzić, czy 3 znalezione liczby rzeczywiście sumują się do zera.$n$$O(n^{2-o(1)})$

2. Najkrótsze ścieżki wszystkich par: biorąc pod uwagę wykres z wagami krawędzi, oblicz jego macierz odległości najkrótszych ścieżek. Czy po otrzymaniu takiej macierzy można szybciej sprawdzić, czy rzeczywiście jest to właściwa macierz odległości, niż ją ponownie obliczyć? Domyślam się, że odpowiedź może być tak, ale z pewnością jest mniej oczywista niż w przypadku 3SUM.

3. Programowanie liniowe. Jeśli podano deklarowane optymalne rozwiązanie, sprawdzenie jest łatwiejsze niż ponowne obliczenie, gdy podane są również informacje pomocnicze (optymalne podwójne rozwiązanie). Z drugiej strony, jeśli dostępne jest tylko pierwotne rozwiązanie, nie jest jasne, czy można to sprawdzić szybciej, niż faktyczne rozwiązanie LP.

Pytanie: co wiadomo na ten temat? To znaczy, kiedy łatwiej jest zweryfikować rozwiązanie problemu w P , niż znaleźć rozwiązanie?

wiadomo, że biorąc pod uwagę wykres G i drzewo T, można zweryfikować w czasie liniowym, że T jest minimalnym drzewem rozpinającym G. Jednak nie mamy jeszcze deterministycznego algorytmu czasu liniowego do obliczenia MST. Oczywiście różnica jest niewielka (1 vs ), ale wciąż tam jest :))$\alpha(n)$

W tym artykule pokazano, że istnieją algorytmy weryfikacji zarówno dla wystąpień TAK, jak i NIE dla 3 problemów, w tym Max flow, 3SUM i APSP, które są szybsze o współczynnik wielomianowy niż znane granice przy obliczaniu samego rozwiązania.

Istnieje pewna klasa problemów, a mianowicie te, które poprawiają czas pracy w trudnych warunkach SETH, których czas weryfikacji weryfikacji instancji NIE jest prawdopodobnie znacznie szybszy niż czas obliczania rozwiązania, w przeciwnym razie domysł z tego dokumentu zwany niedeterministycznym Silna hipoteza czasu wykładniczego by się nie powiodła.

W przypadku niektórych problemów wydaje się, że nie ma różnicy. W szczególności Vassilevska Williams i Williams pokazują:

• w przypadku mnożenia macierzy boolowskich, obliczanie iloczynu macierzy i weryfikowanie ekwiwalentu subkubicznego iloczynu macierzy, co oznacza, że ​​oba mają algorytmy czasu subkubicznego lub żaden z nich nie ma.

• To samo dotyczy obliczania i weryfikacji produktu macierzowego w dowolnej „rozszerzonej (min, +) strukturze” (definicja znajduje się w artykule, ale zawiera wiele naturalnych problemów).

(Teraz, oczywiście, możliwe jest, że wszystkie te problemy mają algorytmy subububowe, a następnie może istnieć wielomianowa różnica między obliczeniami a weryfikacją, ale dla tych problemów nie może być różnicy sześciennej. I wydaje mi się prawdopodobne, że w fakt, że wszystkie wymagają zasadniczo czasu sześciennego).

• Decyzja, czy wartość istnieje w tablicy, wymaga czasu (lub jeśli tablica jest posortowana).$\Omega(n)$$\Omega(\log n)$

  W czasie możliwe jest sprawdzenie, czy tablica zawiera podaną wartość w danej pozycji .$O(1)$

• Sortowanie (w modelu porównawczym) zajmuje czas , ale sprawdzenie, czy tablica lub lista jest posortowana, jest możliwe w czasie .$\Omega(n \log n)$$O(n)$

Myślę, że wiele przykładów pochodzi z problemów NP-zupełnych, które wchodzą w P, gdy naprawimy jeden lub więcej parametrów .

Na przykład sprawdzenie, czy wykres zawiera klikę o rozmiarze jest NP-zupełne, jeśli jest częścią danych wejściowych, a czas rozwiązywalny wielomianowy, jeśli jest ustalony.k $k$$k$$k$

W przypadku dowolnego ustalonego weryfikacja zajmuje czas liniowy, ale o ile , złożoność problemu wyszukiwania (wielomian) zależy od ( .P = N P k Ω ( n k ) $k$$P=NP$$k$$\Omega(n^k) )$

Inne przykłady: znalezienie hamiltonowskiej ścieżki o długości , kolorowanie na ograniczonych wykresach szerokości, ...$k$

Decydująca pierwotność: wydaje się, że najbardziej znany wariant AKS decyduje o pierwotności w czasie , podczas gdy klasyczny certyfikat pierwotności Pratta oznacza, że ​​o pierwszeństwie można decydować w czasie niedeterministycznym . ˜ O (n3$\tilde{O}(n^6)$$\tilde{O}(n^3)$

Papieru przez Abboud et al. ostatnio przyjęty do SODA 2016 pokazuje, że izomorfizm poddrzewa nie może być rozwiązany w czasie chyba że hipoteza silnego wykładniczego czasu jest fałszywa. Oczywiście możemy zweryfikować izomorfizm w czasie liniowym.$O(n^{2-\epsilon})$

Innymi słowy, SETH daje nam naturalny problem w z luką między znajdowaniem a weryfikacją. Ω ( n 1 - ϵ$\sf{P}$$\Omega(n^{1-\epsilon})$

W szczególności algorytm jest znany dla zrootowanych drzew o stałym stopniu (do których nadal obowiązują wyniki dolnej granicy Abbouda i in.). Tak więc w SETH prawie liniowa luka znajdź-zweryfikuj jest zasadniczo wąska dla tego problemu.$O(n^2/\log n)$