Czy są jakieś problemy, które są łatwe do obliczenia, ale trudne do zweryfikowania?

Zakładając, że P NP, problemy z kompletnością NP są „trudne do rozwiązania, ale mają odpowiedzi, które można łatwo sprawdzić”. Czy ma sens rozważenie czegoś przeciwnego, to znaczy problemów, dla których łatwo jest poprawnie obliczyć prawidłową odpowiedź, ale trudno jest zweryfikować dowolne rzekome rozwiązanie? $\neq$

Myślę, że taki problem oznaczałby albo:

Wykładniczo wiele „poprawnych” odpowiedzi na dane dane wejściowe, ponieważ w przeciwnym razie weryfikacja mogłaby zostać przeprowadzona przez obliczenie wszystkich poprawnych odpowiedzi.
Niektóre „poprawne” odpowiedzi są łatwe do obliczenia, ale inne są trudne do znalezienia.

complexity-theory rphv
źródło

Wątpię. Jeśli odpowiedź jest łatwa do obliczenia, wybór certyfikatu jest łatwy: podaj rzekomą odpowiedź z problemem i „sprawdź” odpowiedź, rozwiązując problem i sprawdzając, czy rzekoma odpowiedź jest rzeczywiście odpowiedzią.

Patrick87,

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

@ Patrick87 Solver może być deterministyczny i generować tylko jedną z wszystkich istniejących odpowiedzi. Następnie potrzebujesz skutecznego sposobu sprawdzenia, czy dwa rozwiązania są równoważne. Czy równoważność zestawu może być trudniejsza niż rozwiązanie problemu?

Raphael

Przykro mi, tęskniłem za tą częścią. Mimo to jestem skłonny wątpić w to założenie. Zastanowię się trochę dłużej i wrócę, jeśli będę miał bardziej odpowiednie myśli.

Patrick87,

Certyfikat zwykle oznacza, że nie jest to łatwy sposób, aby zrekonstruować dowód, więc z definicji, jeśli dostarczyć zaświadczenie weryfikacja jest łatwe. Rozwiązanie bez certyfikatu może być trudne.

Gilles „SO- przestań być zły”

Odpowiedzi:

Jeśli masz problemy ze sztucznymi problemami, możesz zrobić wiele z nich. Tu jest kilka:

Biorąc pod uwagę dodatnią liczbę całkowitą n w jedności, odpowiedz na zadowalającą formułę 3CNF w n zmiennych boolowskich.
Nadanie jednej zadowalającej formuły 3CNF jest łatwe, ale decyzja, czy dana formuła 3CNF jest zadowalająca, czy nie, to 3SAT, dobrze znany problem NP-zupełny.
Brak danych wejściowych. Wystarczy odpowiedzieć na maszynę Turinga, która się zatrzymuje (po uruchomieniu z pustą taśmą wejściową).
Danie jednej takiej maszyny Turinga jest łatwe, ale nie można rozstrzygnąć, czy dana maszyna Turinga się zatrzyma, czy nie.

Dodano : Nawiasem mówiąc, nie sądzę, aby to, co napisałeś w ostatnim akapicie, zawiera:

Myślę, że taki problem oznaczałby wykładniczo wiele „poprawnych” odpowiedzi na dane dane wejściowe, ponieważ w przeciwnym razie weryfikacja mogłaby zostać przeprowadzona poprzez obliczenie wszystkich poprawnych odpowiedzi.

Jeśli problem ma jedno rozwiązanie, to rzeczywiście sprawdzenie odpowiedzi nie jest trudniejsze niż obliczenie właściwego rozwiązania. Jeśli jednak problem ma jedno łatwe rozwiązanie i jedno trudne rozwiązanie, nie można skutecznie obliczyć wszystkich rozwiązań. Oto jeden z takich problemów (który jest bardzo sztuczny):

Biorąc pod uwagę maszynę Turinga M , odpowiedz na jedno z następujących stwierdzeń, które są prawdziwe: „ M zatrzymuje się na pustej taśmie wejściowej”, „ M nie zatrzymuje się na pustej taśmie wejściowej”, a „ M to maszyna Turinga”.
Podanie jednego rozwiązania jest łatwe : zawsze możesz wybrać „ M jest maszyną Turinga”. Jednak to, czy dana odpowiedź jest poprawna, czy nie, jest nierozstrzygalne. Zauważ, że w tym problemie są tylko dwa rozwiązania dla każdej instancji.

Tsuyoshi Ito
źródło

Czy istnieje rozsądny sposób formalnego zdefiniowania, co oznacza, że takie problemy są „sztuczne”? (Przez „rozsądny” rozumiem coś, na co możemy się szeroko zgodzić, na przykład stwierdzenie, że definicja „obliczalnego” oddaje naszą intuicję co to znaczy.)

SO Gillesa - przestań być zły ”

@Gilles: Nie, nie sądzę. Nazwałam te problemy „sztucznymi”, ponieważ jest bardzo mało prawdopodobne, że ktoś pierwszy zetknie się z tymi problemami, a następnie odkryje, że łatwo jest udzielić jednej odpowiedzi i trudno jest zdecydować o poprawności danego kandydata na odpowiedź. Ale ta „sztuczność” nie jest żadnym rygorystycznym pojęciem.

Tsuyoshi Ito,

@Tsuyoshi Ito - Dziękujemy za jasną odpowiedź. Zredagowałem ostatni akapit, aby odzwierciedlić twój wgląd.

rphv

Chociaż odpowiedź Tsuyoshi Ito obejmuje „główną” odpowiedź, chciałem dodać dwie subtelniejsze uwagi.

Nawet gdy rozwiązanie jest trudne do zweryfikowania, sprawdzenie rozwiązania jest nadal łatwe do sprawdzenia za pomocą krótkiego ciągu próbnego. Oznacza to, że dzięki rozszerzeniu rozwiązania o dodatkowe informacje można go łatwo sprawdzić; weryfikacja odbywa się zawsze w NP. Jednym ze sposobów na to jest to, że agent obliczający rozwiązanie może zapisać wszystkie losowe bity, których używają, a następnie weryfikator może użyć tego samego losowego ciągu, aby wykonać to samo obliczenie. (Przysłowie musi używać losowych bitów, w przeciwnym razie zawsze wypisuje tę samą odpowiedź, a weryfikator zawsze może łatwo sprawdzić, obliczając odpowiedź tą samą metodą.)
W przypadku komputerów kwantowych jest to bardzo otwarte pytanie. W przypadku klasycznych komputerów weryfikator zawsze może zrobić coś takiego, jak symulacja przysłowia i sprawdzenie, czy otrzymali tę samą odpowiedź. Jest całkiem możliwe, że w przypadku jakiegoś trudnego problemu istnieje algorytm kwantowy, który zapewnia jednolity rozkład wszystkich (wykładniczo wielu) rozwiązań, które są trudne do zweryfikowania. Nie możesz ponownie uruchomić tego przysłowia, ponieważ najprawdopodobniej za każdym razem otrzymasz inną odpowiedź.

Jako przykład podobnego problemu cierpi z tego powodu problem Deutsch-Jozsa. Jeśli wyrocznia nie jest funkcją zrównoważoną, to komputer kwantowy może szybko stwierdzić, że tak jest, ale nie ma krótkiego dowodu, który pozwoliłby klasycznemu komputerowi to zweryfikować. (Jest to tylko „podobny” problem, ponieważ nadal może być sprawdzony przez inny komputer kwantowy, a sprawdzanie odbywa się również w klasycznym BPP, nawet jeśli nie jest w P.)

Alex Meiburg
źródło