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

52

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.nO(n2o(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?

Andras Farago
źródło
7
Myślę, że wiele przykładów pochodzi z problemów NP-zupełnych, które wchodzą w P, gdy naprawimy niektóre parametry. Na przykład sprawdzenie, czy wykres zawiera klikę o rozmiarze dla ustalonego . Weryfikacja trwa liniowo, ale chyba że P = NP, złożoność problemu wyszukiwania (wielomian) zależy odkkk
Marzio De Biasi
16
Możemy sprawdzić, czy lista liczb całkowitych jest posortowana za porównań , ale do posortowania nieposortowanej listy potrzeba porównań . nn1Θ(nlogn)
Thomas
7
Czy chcesz, aby weryfikacja zarówno przypadków tak, jak i nie wystąpiła w przypadku problemów decyzyjnych była łatwa? W przypadku 3SUM, chociaż łatwo jest zweryfikować instancje tak w stałym czasie, nie wiem, czy łatwo jest zweryfikować instancje brak. A może myślisz bardziej zgodnie z problemami, w których występuje wyjście nie-boolowskie, takie jak mnożenie macierzy? (Mnożenie macierzy jest przykładem tego, czego chcesz, jeśli zezwolisz na algorytmy losowe.)
Robin Kothari,
3
„Z drugiej strony weryfikacja rozwiązania jest znacznie szybsza, ponieważ wystarczy tylko sprawdzić, czy 3 znalezione liczby rzeczywiście sumują się do zera”. - Musimy również sprawdzić, czy 3 znalezione liczby są faktycznie częścią danych wejściowych.
hvd
3
Czy istnieją problemy, dla których wiemy, że weryfikacja nie jest łatwiejsza?
Raphael,

Odpowiedzi:

24

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 :))α(n)

Suresh Venkat
źródło
4
Może warto dodać, że istnieje algorytm losowy, który działa w oczekiwanym czasie liniowym (algorytm Karger-Klein-Tarjan).
Sasho Nikolov
2
Ponadto, jeśli ktoś chce łącza, jest to najprostszy algorytm weryfikacji MST w czasie liniowym, jaki znam : webhome.cs.uvic.ca/~val/Publications/Al Algorytmica-MSTverif.ps .
Sasho Nikolov
20

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.

Thatchaphol
źródło
18

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).

Joshua Grochow
źródło
2
Z drugiej strony, do mnożenia macierzy w wystarczająco dużym polu istnieje algorytm randomizowany w czasie kwadratowym do weryfikacji, a najszybszy czas obliczania produktu to n omega.
Thatchaphol,
2
@Thatchaphol: Tak, choć wiele osób uważa, że ​​omega = 2 ... Powszechnie wiadomo, że mnożenie macierzy boolowskiej (tj. Mnożenie macierzy obliczeniowej przez wartość logiczną i / lub pół-pierścień) ma nieco inną naturę niż mnożenie macierzy przez pole.
Joshua Grochow
16
  • Decyzja, czy wartość istnieje w tablicy, wymaga czasu (lub jeśli tablica jest posortowana).Ω(n)Ω(logn)

    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 .Ω(nlogn)O(n)

Raphael
źródło
2
Podobnie: określenie, czy istnieje duplikat elementu, to w modelu porównawczym, ale oczywiście można to sprawdzić w . O ( 1 )Ω(nlogn)O(1)
SamM
@SMM: Masz na myśli weryfikację w ? Co dokładnie otrzymałeś? Czuję, że dokonujesz niesprawiedliwego porównania. O(n)
Mehrdad
@ Mehrdad dobry punkt; jeśli podano wartość (a nie indeksy), należy zweryfikować . Widzę dobry argument, że jest to lepszy sposób, aby na to spojrzeć. Θ(n)
SamM
10

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 kkkk

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 ) )kP=NPkΩ(nk))

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

Marzio De Biasi
źródło
9

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)O~(n6)O~(n3)

Joe Bebel
źródło
dopełnienie (złożoność) jest jeszcze łatwiejsze do zauważenia!
Yonatan 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(n2ϵ)

Innymi słowy, SETH daje nam naturalny problem w z luką między znajdowaniem a weryfikacją. Ω ( n 1 - ϵ )PΩ(n1ϵ)

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(n2/logn)

SamM
źródło