Jestem na kursie informatyki i złożoności i nie jestem w stanie zrozumieć, co oznaczają te terminy.

Wiem tylko, że NP to podzbiór NP-zupełny, który jest podzbiorem NP-trudnym, ale nie mam pojęcia, co one właściwie oznaczają. Wikipedia też nie jest zbyt pomocna, ponieważ wyjaśnienia są wciąż trochę za wysokie.

Myślę, że artykuły z Wikipedii $\mathsf{P}$ , $\mathsf{NP}$ i $\mathsf{P}$ vs. $\mathsf{NP}$ są całkiem dobre. Nadal jest to, co powiedziałbym: Część I , Część II

[Wykorzystam uwagi w nawiasach, aby omówić niektóre szczegóły techniczne, które możesz pominąć, jeśli chcesz.]

Część I

Problemy decyzyjne

Istnieją różne rodzaje problemów obliczeniowych. Jednak we wprowadzeniu do kursu teorii złożoności obliczeniowej łatwiej jest skupić się na problemie decyzyjnym , tj. Problemach, w których odpowiedź brzmi TAK lub NIE. Istnieją inne rodzaje problemów obliczeniowych, ale w większości przypadków pytania na ich temat można sprowadzić do podobnych pytań dotyczących problemów decyzyjnych. Ponadto problemy decyzyjne są bardzo proste. Dlatego we wprowadzeniu do kursu teorii złożoności obliczeniowej skupiamy naszą uwagę na badaniu problemów decyzyjnych.

Możemy zidentyfikować problem decyzyjny z podzbiorem danych wejściowych, które mają odpowiedź TAK. Upraszcza zapisu i pozwala zapisu $x\in Q$ w miejscu $Q(x)=YES$ i $x \notin Q$ zamiast $Q(x)=NO$ .

Inna perspektywa polega na tym, że mówimy o zapytaniach członkowskich w zestawie. Oto przykład:

Problem decyzyjny:

Dane wejściowe: Liczba naturalna $x$ ,
Pytanie: Czy $x$ jest liczbą parzystą?

Problem członkostwa:

Dane wejściowe: Liczba naturalna $x$ ,
Pytanie: Czy $x$ w $Even = \{0,2,4,6,\cdots\}$ ?

Odnosimy się do odpowiedzi TAK na wejściu jako akceptacji wejścia i do odpowiedzi NIE na wejściu jako odrzucenia wejścia.

Przyjrzymy się algorytmom pod kątem problemów decyzyjnych i omówimy wydajność tych algorytmów w wykorzystaniu zasobów obliczalnych . Będę polegać na Twojej intuicji programowania w języku takim jak C zamiast formalnego zdefiniowania tego, co rozumiemy przez algorytm i zasoby obliczeniowe.

[Uwagi: 1. Gdybyśmy chcieli zrobić wszystko formalnie i dokładnie, musielibyśmy naprawić model obliczeniowy, taki jak standardowy model maszyny Turinga, aby precyzyjnie zdefiniować, co rozumiemy przez algorytm i jego wykorzystanie zasobów obliczeniowych. 2. Jeśli chcemy porozmawiać o obliczeniach dotyczących obiektów, których model nie może bezpośrednio obsłużyć, musielibyśmy zakodować je jako obiekty, które może obsłużyć model maszyny, np. Jeśli używamy maszyn Turinga, musimy zakodować obiekty takie jak liczby naturalne i wykresy jako ciągi binarne.]

$\mathsf{P}$ = Problemy ze skutecznymi algorytmamiznajdowaniarozwiązań

Załóżmy, że wydajne algorytmy oznaczają algorytmy wykorzystujące co najwyżej wielomianową ilość zasobów obliczeniowych. Głównym zasobem, na którym nam zależy, jest najgorszy czas działania algorytmów w odniesieniu do wielkości wejściowej, tj. Liczba podstawowych kroków, jakie algorytm podejmuje na wejściu o wielkości $n$ . Rozmiar wejścia $x$ wynosi $n$ jeśli potrzeba $n$ bitów pamięci komputera do przechowywania $x$ , w którym to przypadku piszemy $|x| = n$ . Więc przez wydajnych algorytmów rozumiemy algorytmy, które mają wielomianu najgorszy czas działa .

Założenie , że algorytmy Wielomian czasu uchwycić intuicyjne pojęcie wydajnych algorytmów jest znany jako tezy Cobham . Nie będę w tym miejscu dyskutować, czy $\mathsf{P}$ jest właściwym modelem dla sprawnie rozwiązywalnych problemów i czy $\mathsf{P}$ przechwytuje, czy nie przechwytuje to, co można skutecznie obliczyć w praktyce i powiązane kwestie. Na razie istnieją dobre powody, aby przyjąć to założenie, więc naszym celem jest założenie, że tak właśnie jest. Jeśli nie zaakceptujesz tezy Cobhama, nie spowoduje to, że to, co piszę poniżej, będzie niepoprawne, jedyną rzeczą, którą stracimy, jest intuicja o wydajnym obliczeniu w praktyce. Myślę, że jest to pomocne założenie dla kogoś, kto zaczyna uczyć się teorii teorii złożoności.

$\mathsf{P}$ jest klasą problemów decyzyjnych, które można skutecznie rozwiązać,
tj. Problemów decyzyjnych, które mają algorytmy czasu wielomianowego.

Mówiąc bardziej formalnie, mówimy, że problem decyzyjny $Q$ występuje w $\mathsf{P}$ iff

jest skuteczny algorytm taki sposób, że wszystkie wejścia x ,$A$
$x$

• jeśli $Q(x)=YES$ to $A(x)=YES$ ,
• jeżeli $Q(x)=NO$ wówczas $A(x)=NO$ .

Mogę po prostu napisać $A(x)=Q(x)$ , ale piszę to w ten sposób, więc możemy porównać go do definicji $\mathsf{NP}$ .

$\mathsf{NP}$ = Problemy ze skutecznymi algorytmamiweryfikacjidowodów / certyfikatów / świadków

Czasami nie znamy żadnego skutecznego sposobu znalezienia odpowiedzi na problem decyzyjny, jednak jeśli ktoś powie nam odpowiedź i da nam dowód , możemy skutecznie sprawdzić , czy odpowiedź jest poprawna, sprawdzając dowód, czy jest to prawidłowy dowód . To Ideą złożoność klasa $\mathsf{NP}$ .

Jeśli dowód jest zbyt długi, to nie jest tak naprawdę przydatny, może to potrwać zbyt długo, aby po prostu przeczytać dowód, nie mówiąc już o sprawdzeniu, czy jest ważny. Chcemy, aby czas potrzebny na weryfikację był rozsądny w stosunku do rozmiaru oryginalnego wejścia, a nie rozmiaru danego dowodu! Oznacza to, że tak naprawdę nie chcemy arbitralnych długich dowodów, ale krótkich dowodów. Zauważ, że jeśli czas działania weryfikatora jest wielomianowy pod względem wielkości oryginalnego wejścia, wówczas może odczytać tylko wielomianową część dowodu. Mówiąc krótko, mamy na myśli rozmiar wielomianu .

Od tego momentu używaj słowa „dowód”, mam na myśli „krótki dowód”.

Oto przykład problemu, którego nie wiemy jak skutecznie rozwiązać, ale możemy skutecznie zweryfikować dowody:

Partition
Input: skończony zbiór liczb naturalnych $S$ ,
Pytanie: czy można podzielić $S$ na dwa zbiory $A$ i $B$ ( $A \cup B = S$ i $A \cap B = \emptyset$ )
tak, aby suma liczb w $A$ była równa suma liczby w $B$ ( $\sum_{x\in A}x=\sum_{x\in B}x$ )?

Jeśli dam ci $S$ i zapytam, czy możemy podzielić go na dwa zestawy, aby ich sumy były równe, nie znasz żadnego skutecznego algorytmu, aby go rozwiązać. Prawdopodobnie spróbujesz wszystkich możliwych sposobów podziału liczb na dwa zestawy, aż znajdziesz partycję, w której sumy są równe, lub dopóki nie wypróbujesz wszystkich możliwych partycji i żaden z nich nie zadziała. Jeśli któryś z nich zadziałał, powiedziałbyś TAK, w przeciwnym razie powiedziałbyś NIE.

Ale istnieje wykładniczo wiele możliwych partycji, więc zajmie to dużo czasu. Jednak jeśli dam ci dwa zbiory $A$ i $B$ , można łatwo sprawdzić, czy kwoty są równe, jeśli $A$ i $B$ jest rozbiór $S$ . Pamiętaj, że możemy skutecznie obliczać kwoty.

Tutaj para $A$ i $B$ które ci daję, jest dowodem na odpowiedź TAK. Możesz skutecznie zweryfikować moje roszczenie, sprawdzając mój dowód i sprawdzając, czy jest to prawidłowy dowód . Jeśli odpowiedź brzmi TAK, oznacza to, że istnieje ważny dowód, który mogę ci przekazać, a Ty możesz go skutecznie zweryfikować. Jeśli odpowiedź brzmi NIE, nie ma ważnego dowodu. Więc cokolwiek ci dam, możesz sprawdzić i zobaczyć, że nie jest to ważny dowód. Nie mogę oszukać cię niepoprawnym dowodem, że odpowiedź brzmi TAK. Przypomnijmy, że jeśli dowód jest zbyt duży, jego weryfikacja zajmie dużo czasu, nie chcemy, aby tak się stało, dlatego dbamy tylko o wydajne dowody, tj. Dowody o wielomianowym rozmiarze.

Czasami ludzie używają „ zaświadczenia ” lub „ świadka ” zamiast „dowodu”.

Uwaga Daję ci wystarczająco dużo informacji o odpowiedzi dla danego wejścia $x$ , abyś mógł skutecznie znaleźć i zweryfikować odpowiedź. Na przykład w naszym przykładzie partycji nie powiem ci odpowiedzi, po prostu daję ci partycję i możesz sprawdzić, czy jest poprawna, czy nie. Pamiętaj, że musisz sam zweryfikować odpowiedź, nie możesz mi ufać w to, co mówię. Ponadto możesz tylko sprawdzić poprawność mojego dowodu. Jeśli mój dowód jest ważny, oznacza to, że odpowiedź brzmi TAK. Ale jeśli mój dowód jest nieważny, nie oznacza to, że odpowiedź brzmi NIE. Widziałeś, że jeden dowód był nieważny, nie że nie ma ważnych dowodów. Mówimy o dowodach na TAK. Nie mówimy o dowodach na NIE.

Spójrzmy na przykład: $A=\{2,4\}$ i $B=\{1,5\}$ jest dowodem na to, że $S=\{1,2,4,5\}$ można podzielić na dwa zestawy z jednakowymi sumami. Musimy po prostu zsumować liczby w $A$ i numery w $B$ i sprawdzić, czy wyniki są równe, i sprawdzić, czy , B jest rozbiór S .$A$$B$$S$

Jeśli dałem ci $A=\{2,5\}$ i $B=\{1,4\}$ , sprawdzisz i zobaczysz, że mój dowód jest nieważny. Nie oznacza to, że odpowiedź brzmi NIE, to po prostu oznacza, że ​​ten konkretny dowód był nieważny. Twoim zadaniem tutaj nie jest znalezienie odpowiedzi, ale jedynie sprawdzenie, czy otrzymany dowód jest ważny.

To tak, jak student rozwiązujący pytanie na egzaminie i profesor sprawdzający, czy odpowiedź jest poprawna. :) (niestety często studenci nie udzielają wystarczających informacji, aby zweryfikować poprawność swojej odpowiedzi, a profesorowie muszą odgadnąć resztę swojej częściowej odpowiedzi i zdecydować, ile ocen powinni dać uczniom za częściowe odpowiedzi, co jest dość trudne zadanie).

Zadziwiające jest to, że ta sama sytuacja dotyczy wielu innych naturalnych problemów, które chcemy rozwiązać: możemy skutecznie zweryfikować, czy dany krótki dowód jest ważny, ale nie znamy żadnego skutecznego sposobu na znalezienie odpowiedzi . Właśnie z tego powodu klasa złożoności $\mathsf{NP}$ jest niezwykle interesująca (choć nie była to pierwotna motywacja do jej zdefiniowania). Cokolwiek robisz (nie tylko w CS, ale także w matematyce, biologii, fizyce, chemii, ekonomii, zarządzaniu, socjologii, biznesie, ...) napotkasz problemy obliczeniowe, które należą do tej klasy. Aby zorientować się, jak wiele problemów okazują się być w $\mathsf{NP}$ wymeldowania kompendium problemów optymalizacji NP . Rzeczywiście można mieć trudności ze znalezieniem naturalnych problemów, które nie są w $\mathsf{NP}$ . To jest po prostu niesamowite.

$\mathsf{NP}$ to klasa problemów, które mają wydajne weryfikatory, tzn.
Istnieje algorytm wielomianowy, który może sprawdzić, czy dane rozwiązanie jest poprawne.

Mówiąc bardziej formalnie, mówimy, że problem decyzyjny $Q$ występuje w $\mathsf{NP}$ iff

istnieje skuteczny algorytm $V$ zwany weryfikatorem, taki że
dla wszystkich danych wejściowych $x$ ,

• jeśli $Q(x)=YES$ to istnieje dowód $y$ taki, że $V(x,y)=YES$ ,
• Jeżeli $Q(x)=NO$ to dla wszystkich dowodów, $y$ , $V(x,y)=NO$ .

Mówimy, że weryfikator jest zdrowy, jeśli nie przyjmuje żadnego dowodu, gdy odpowiedź brzmi NIE. Innymi słowy, nie można oszukać weryfikatora dźwięku, aby zaakceptował dowód, jeśli odpowiedź brzmi NIE. Bez fałszywych trafień.

Podobnie mówimy, że weryfikator jest kompletny, jeśli akceptuje co najmniej jeden dowód, gdy odpowiedź brzmi TAK. Innymi słowy, kompletny weryfikator może być przekonany, że odpowiedź brzmi TAK.

Terminologia pochodzi z systemów logicznych i sprawdzających . Nie możemy używać dźwiękoszczelnego systemu do udowodnienia fałszywych oświadczeń. Możemy użyć kompletnego systemu dowodowego, aby udowodnić wszystkie prawdziwe stwierdzenia.

Weryfikator $V$ otrzymuje dwa wejścia,

• $x$ : oryginalne wejście dla$Q$ , i
• $y$ : sugerowane dowód$Q(x)=YES$ .

Zauważ, że chcemy, aby $V$ był skuteczny w rozmiarze $x$ . Jeśli $y$ jest wielkim dowodem weryfikator będzie mógł odczytać tylko wielomianu część z $y$ . Dlatego wymagamy, aby dowody były krótkie. Jeśli $y$ jest krótkie, powiedzenie, że $V$ jest wydajne w $x$ jest równoznaczne z powiedzeniem, że $V$ jest wydajne w $x$ i $y$ (ponieważ rozmiar $y$ jest ograniczony stałym wielomianem o wielkości $x$ ).

Podsumowując, aby pokazać, że problem decyzyjny $Q$ występuje w $\mathsf{NP}$ musimy podać wydajny algorytm weryfikatora, który jest solidny i kompletny .

Nota historyczna: historycznie nie jest to oryginalna definicja $\mathsf{NP}$ . Oryginalna definicja wykorzystuje tzw niedeterministyczne maszyny Turinga. Maszyny te nie odpowiadają żadnemu faktycznemu modelowi maszyny i trudno się do nich przyzwyczaić (przynajmniej wtedy, gdy zaczynasz poznawać teorię złożoności). Czytałem, że wielu ekspertów uważa, że ​​zastosowaliby definicję weryfikatora jako definicję główną, a nawet nazwaliby klasę $\mathsf{VP}$ (do weryfikacji w czasie wielomianowym) zamiast $\mathsf{NP}$ jeśli wrócą do początków teorii złożoności obliczeniowej. Definicja weryfikator jest bardziej naturalne, łatwiej zrozumieć koncepcyjnie i łatwiejsze w użyciu, aby pokazać problemy są w $\mathsf{NP}$ .

$\mathsf{P}\subseteq \mathsf{NP}$

Dlatego mamy $\mathsf{P}$ = skuteczny do rozwiązania i $\mathsf{NP}$ = sprawnie weryfikowalny . Zatem $\mathsf{P}=\mathsf{NP}$ iff problemy, które można skutecznie zweryfikować, są takie same jak problemy, które można skutecznie rozwiązać.

Zauważ, że każdy problem w $\mathsf{P}$ występuje również w $\mathsf{NP}$ , tzn. Jeśli możesz rozwiązać problem, możesz również sprawdzić, czy dany dowód jest poprawny: weryfikator po prostu zignoruje dowód!

Jest tak, ponieważ nie potrzebujemy go, weryfikator może samodzielnie obliczyć odpowiedź, może zdecydować, czy odpowiedź jest TAK czy NIE bez żadnej pomocy. Jeśli odpowiedź brzmi NIE, wiemy, że nie powinno być żadnych dowodów, a nasz weryfikator po prostu odrzuci każdy sugerowany dowód. Jeśli odpowiedź jest twierdząca, nie powinno być dowód, aw rzeczywistości będzie po prostu przyjąć wszystko jako dowodu.

[Mogliśmy sprawić, że nasz weryfikator zaakceptuje tylko niektóre z nich, to również dobrze, pod warunkiem, że nasz weryfikator zaakceptuje co najmniej jeden dowód, że weryfikator działa poprawnie dla problemu.]

Oto przykład:

Suma
wejściowa: lista $n+1$ liczb naturalnych $a_1,\cdots,a_n$ , i $s$ ,
Pytanie: czy $\Sigma_{i=1}^n a_i = s$ ?

Problem tkwi w $\mathsf{P}$ ponieważ możemy zsumować liczby, a następnie porównać je z $s$ , zwracamy TAK, jeśli są równe, i NIE, jeśli nie są.

Problemem jest również $\mathsf{NP}$ . Zastanów się nad weryfikatorem $V$ który dostaje dowód plus dane wejściowe dla Sum. Działa tak samo, jak algorytm w $\mathsf{P}$ , który opisaliśmy powyżej. Jest to skuteczny weryfikator sumy.

Zauważ, że istnieją inne skuteczne weryfikatory sumy, a niektórzy z nich mogą użyć dostarczonego im dowodu. Jednak ten, który zaprojektowaliśmy, nie działa i to też dobrze. Ponieważ daliśmy wydajnego weryfikatora dla Sum problem jest w $\mathsf{NP}$ . Ten sam trik działa dla wszystkich innych problemów $\mathsf{P}$ więc $\mathsf{P} \subseteq \mathsf{NP}$ .

Algorytmy brutalnej siły / wyczerpujące wyszukiwanie dla $\mathsf{NP}$ i $\mathsf{NP}\subseteq \mathsf{ExpTime}$

Najlepsze algorytmy znamy od rozwiązywania dowolnego problemu w $\mathsf{NP}$ są brute-force / wyczerpująca-wyszukiwania algorytmy. Odbiór wydajnego weryfikatora do problemu (ma skutecznego weryfikatora przez naszego założenia, że jest w $\mathsf{NP}$ ) i sprawdzaniu wszystkich możliwych dowodów, jeden po drugim. Jeśli weryfikator zaakceptuje jeden z nich, odpowiedź brzmi TAK. W przeciwnym razie odpowiedź brzmi NIE.

W naszym przykładzie partycji wypróbowujemy wszystkie możliwe partycje i sprawdzamy, czy sumy są równe w którejkolwiek z nich.

$m$$2^m$

$\mathsf{NP}$$\mathsf{NP}\subseteq \mathsf{ExpTime}$$\mathsf{NP}\subseteq \mathsf{PSpace}$

$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}=\mathsf{P}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\subseteq\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$

Dolne granice wydają się trudne do udowodnienia

$\mathsf{NP}$

Niestety zadanie udowodnienia dolnych granic jest bardzo trudne. Nie możemy nawet udowodnić, że problemy te wymagają więcej niż czasu liniowego ! Nie mówiąc już o wymagającym czasie wykładniczym.

Udowodnienie dolnych granic czasu liniowego jest raczej łatwe: algorytm musi przecież odczytać dane wejściowe. Udowadnianie superliniowych dolnych granic to zupełnie inna historia. Możemy udowodnić superliniowe dolne granice z większą liczbą ograniczeń dotyczących rodzaju rozważanych algorytmów, np. Sortowanie algorytmów za pomocą porównania, ale nie znamy dolnych granic bez tych ograniczeń.

Aby udowodnić górną granicę problemu, wystarczy zaprojektować wystarczająco dobry algorytm. Często potrzebuje wiedzy, kreatywnego myślenia, a nawet pomysłowości, aby wymyślić taki algorytm.

Jednak zadanie jest znacznie prostsze w porównaniu do udowodnienia dolnej granicy. Musimy pokazać, że nie ma dobrych algorytmów . Nie dlatego, że nie znamy obecnie wystarczająco dobrych algorytmów, ale że nie ma żadnych dobrych algorytmów , że nikt nigdy nie wymyśli dobrego algorytmu . Pomyśl o tym przez chwilę, jeśli jeszcze tego nie zrobiłeś, jak możemy pokazać taki wynik niemożliwości ?

$1=0$

Aby udowodnić dolny pułap, czyli wykazać, że problem wymaga trochę czasu na rozwiązanie oznacza, że mamy do udowodnienia, że każdy$\mathsf{NP}$problemy, np. chciwy i jego rozszerzenia nie mogą działać, a niektóre prace związane są z algorytmami programowania dynamicznego, a także prace nad konkretnymi sposobami programowania liniowego. Ale nie są nawet bliskie wykluczenia inteligentnych pomysłów, które znamy (poszukaj niższych granic w ograniczonych modelach obliczeniowych, jeśli jesteś zainteresowany).

Bariery: dolne granice są trudne do udowodnienia

Z drugiej strony mamy wyniki matematyczne zwane barierami, które mówią, że dowód z dolnej granicy nie może być taki i taki, a taki i taki prawie obejmuje wszystkie techniki, których użyliśmy do udowodnienia niższych granic! W rzeczywistości wielu badaczy zrezygnowało z pracy nad udowodnieniem dolnych granic po uzyskaniu przez barierę naturalnych dowodów Aleksandra Razbarowa i Stevena Rudicha . Okazuje się, że istnienie określonego rodzaju dowodów o niższej granicy oznaczałoby brak bezpieczeństwa kryptograficznych generatorów liczb pseudolosowych i wielu innych narzędzi kryptograficznych.

Mówię prawie dlatego, że w ostatnich latach nastąpił pewien postęp, głównie przez Ryana Williamsa , który był w stanie inteligentnie ominąć wyniki bariery, jednak wyniki do tej pory są dla bardzo słabych modeli obliczeń i dość daleko od wykluczenia ogólnych algorytmów czasu wielomianowego .

$\mathsf{NP}$

[Z drugiej strony praca Ryana Williamsa pokazuje, że istnieją ścisłe powiązania między udowodnieniem dolnych granic a udowodnieniem górnych granic. Jeśli jesteś zainteresowany, zobacz jego przemówienie na ICM 2014. ]

Redukcje: Rozwiązywanie problemu przy użyciu innego problemu jako podprogramu / Oracle / czarnej skrzynki

Idea redukcji jest bardzo prosta: aby rozwiązać problem, użyj algorytmu dla innego problemu.

$n$$Sum$$Sum$

Problem:

$n$$x_1,\ldots,x_n$
$\sum_{i=1}^{n} x_i$

Algorytm redukcji:

1. $s = 0$
2. $i$$1$$n$
   $s = Sum(s,x_i)$
3. $s$

$Sum$$Sum$$Sum$$Sum$

Zasadniczo jest to redukcja: załóżmy, że mamy algorytm dla problemu i używamy go jako wyroczni, aby rozwiązać inny problem. Wydajność oznacza efektywność przy założeniu, że wyrocznia odpowiada w jednostce czasu, tj. Liczymy każde wykonanie wyroczni w jednym kroku.

Jeśli wyrocznia zwraca dużą odpowiedź, musimy ją przeczytać, a to może zająć trochę czasu, więc powinniśmy policzyć czas, jaki zajmuje nam przeczytanie odpowiedzi, którą dał nam wyrocznia. Podobnie do pisania / zadawania pytania z wyroczni. Ale wyrocznia działa natychmiast, tzn. Gdy tylko zadamy pytanie z wyroczni, wyrocznia wypisze nam odpowiedź w ciągu jednej jednostki czasu. Cała praca wykonywana przez wyrocznię liczy się jako jeden krok, ale nie obejmuje to czasu, który zajmuje nam napisanie pytania i przeczytanie odpowiedzi.

Ponieważ nie obchodzi nas, jak działa wyrocznia, a jedynie odpowiedzi, które zwraca, możemy uprościć i uznać wyrocznię za sam problem zamiast algorytmu. Innymi słowy, nie obchodzi nas, czy wyrocznia nie jest algorytmem, nie obchodzi nas, w jaki sposób wyrocznia wymyśla odpowiedzi.

$Sum$

Możemy zadawać wiele pytań z wyroczni, a pytania nie muszą być ustalone z góry: możemy zadać pytanie i na podstawie odpowiedzi, którą zwraca wyrocznia, sami wykonujemy obliczenia, a następnie zadajemy kolejne pytanie w oparciu o otrzymaną odpowiedź poprzednie pytanie.

Innym sposobem spojrzenia na to jest myślenie o tym jako o interaktywnym obliczeniu . Interaktywne obliczenia same w sobie są dużym tematem, więc nie będę się tutaj zajmował, ale myślę, że wspomnienie tej perspektywy redukcji może być pomocne.

$A$$O$$A^O$

Zmniejszenie to omówiono powyżej, najbardziej ogólnie postać redukcji i znany jest jako zmniejszenie czarnej skrzynki (aka redukcji oracle , redukcji Turinga ).

Bardziej formalnie:

$Q$$O$$Q \leq_T O$
$A$$x$
$Q(x) = A^O(x)$

$A$$O$$Q$

$A$$Q\leq^\mathsf{P}_T O$$T$

Jednak możemy chcieć wprowadzić pewne ograniczenia w sposobie interakcji algorytmu redukcji z wyrocznią. Istnieje kilka ograniczeń, które są badane, ale najbardziej użytecznym ograniczeniem jest ograniczenie zwane wielokrotnością jeden (inaczej zwane redukcjami mapowania ).

$x$$y$

Bardziej formalnie,

$Q$$O$$Q \leq_m O$
$A$$x$
$Q(x) = O(A(x))$

$Q \leq_m^\mathsf{P} O$

$\mathsf{NP}$$A$$\mathsf{NP}$$B$$A$$\mathsf{NP}$

$\mathsf{P}$$\mathsf{NP}$$\mathsf{NP}$

Wpis stał się zbyt długi i przekracza limit odpowiedzi (30000 znaków). Będę kontynuować odpowiedź w części II .

część druga

Kontynuacja z części I .

Poprzedni przekroczył maksymalną liczbę liter dozwoloną w odpowiedzi (30000), więc dzielę ją na dwie części.

$\mathsf{NP}$ $\mathsf{NP}$

$\mathsf{P}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Teraz czasami chcemy powiedzieć, że problem jest trudny do rozwiązania . Ale, jak wspomniano powyżej, nie możemy wykorzystywać dolnych granic w tym celu: teoretycznie są one dokładnie tym, co chcielibyśmy udowodnić, jednak w praktyce nie udało nam się udowodnić dolnych granic i ogólnie trudno je udowodnić, jak wspomnieliśmy powyżej. Czy nadal można powiedzieć, że problem jest trudny do rozwiązania ?

$\mathsf{NP}$$\mathsf{NP}$

Redukcje jako względne trudności

$A$$B$$A$$B$$\leq$

$A$$B$$A$$B$

$M^B$$A$$B$$M$$B$$A$$N$$B$$M^B$$N$$M^N$$A$

$\mathsf{P}$

$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$
$\mathsf{NP}$$\mathsf{NP}$

$A$$\mathsf{NP}$

$A$$\mathsf{NP}$
$\mathsf{NP}$$B$$B$$A$$B\leq_m^\mathsf{P} A$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$

(Dwa inne problemy, przy których wiele osób pracuje nad optymalizacją algorytmów w celu praktycznego wykorzystania w przemyśle, to programowanie liczb całkowitych i problem dotyczący satysfakcji z ograniczeń . W zależności od problemu i przypadków, dla których zależy Ci na zoptymalizowanych algorytmach, jeden z nich może działać lepiej niż inni.)

$\mathsf{NP}$
$\mathsf{NP}$

$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$ twardy (tzn. nie ma żadnego algorytmu wielomianowego czasu).

Teraz pytania są następujące:

• $\mathsf{NP}$

• Czy znamy któreś z nich?

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{ExpTime}$$\mathsf{NP}$$\mathsf{NP}$

$p \lor \lnot p$

$\mathsf{NP}$$\mathsf{NP}$

$A$$\mathsf{NP}$$A$$B$$B$$\mathsf{NP}$$\mathsf{NP}$$A$$A$$B$$\mathsf{NP}$$B$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$

$SAT$$\mathsf{NP}$$SAT$$SubsetSum$$\mathsf{NP}$$SAT$$SubsetSum$

$\mathsf{NP}$

$\mathsf{NP}$

Uwaga: poniższa część może być nieco techniczna przy pierwszym czytaniu.

$\mathsf{NP}$

$V$$x$$t$$k$
$YES$$k$$V$$x$$t$$NO$

$UniVer$$\mathsf{NP}$

$V$$\mathsf{NP}$$x$$V$$x$$UniVer$
$t$$k$$V$$x$$V$$x$

$t$$t$$t$$k$

$\mathsf{NP}$$UniVer$$\mathsf{NP}$

$M$$x$$M$$t$
$YES$$M$$x$$YES$$t$$NO$$YES$$t$

$C$$\mathsf{P}$$t$

$Interpreter$

$UniVer$$\mathsf{NP}$$M$$x$$t$$k$$c$$c$$k$$Interpreter$$M$$YES$$x$$c$$t$

$SAT$$\mathsf{NP}$

$UniVer$$\mathsf{NP}$$UniVer$$\mathsf{NP}$

$\mathsf{NP}$$SAT$

$SAT$

$\varphi$
$YES$$\varphi$$NO$

$SAT$$\mathsf{NP}$

Do napisania...

$\mathsf{NP}$

$\mathsf{NP}$

$\mathsf{NP}$

$\mathsf{P}$$\mathsf{NP}$

Co dalej? Dokąd się udać?

Więcej niż użyteczny wymienione odpowiedzi, polecam bardzo do obejrzenia „ Beyond Obliczenie: P vs NP problem ” przez Michaela Sipser . Myślę, że ten film powinien zostać zarchiwizowany jako jeden z wiodących filmów dydaktycznych w dziedzinie informatyki.!

Cieszyć się!

Kopiowanie mojej odpowiedzi na podobne pytanie dotyczące przepełnienia stosu:

Najłatwiejszym sposobem wyjaśnienia P v. NP i tym podobnych bez wchodzenia w szczegóły techniczne jest porównanie „problemów słownych” z „problemami wielokrotnego wyboru”.

Kiedy próbujesz rozwiązać „problem słowny”, musisz znaleźć rozwiązanie od zera. Kiedy próbujesz rozwiązać „problemy wielokrotnego wyboru”, masz wybór: albo rozwiąż je jak „problem słowny”, albo spróbuj podłączyć każdą z udzielonych odpowiedzi i wybierz odpowiedź kandydata, która pasuje.

Często zdarza się, że „problem wielokrotnego wyboru” jest znacznie łatwiejszy niż odpowiadający mu „problem słowny”: zastąpienie odpowiedzi kandydata i sprawdzenie, czy pasują, może wymagać znacznie mniej wysiłku niż znalezienie właściwej odpowiedzi od zera.

Teraz, jeśli zgodzilibyśmy się, że wysiłek, który zajmuje czas wielomianowy „łatwo”, wówczas klasa P składałaby się z „łatwych problemów słownych”, a klasa NP składałaby się z „łatwych problemów wielokrotnego wyboru”.

Istotą P przeciwko NP jest pytanie: „Czy są jakieś łatwe problemy wielokrotnego wyboru, które nie są łatwe jak problemy słowne”? To znaczy, czy są problemy, dla których łatwo jest zweryfikować poprawność danej odpowiedzi, ale znalezienie odpowiedzi od podstaw jest trudne?

Teraz, gdy intuicyjnie rozumiemy, czym jest NP, musimy rzucić wyzwanie naszej intuicji. Okazuje się, że istnieją „problemy wielokrotnego wyboru”, które w pewnym sensie są najtrudniejsze ze wszystkich: gdyby ktoś znalazł rozwiązanie jednego z tych „najtrudniejszych ze wszystkich” problemów, byłby w stanie znaleźć rozwiązanie WSZYSTKIEGO Problemy NP! Kiedy Cook odkrył to 40 lat temu, było to całkowitą niespodzianką. Te „najtrudniejsze ze wszystkich” problemy są znane jako NP-trudne. Jeśli znajdziesz „rozwiązanie problemu słownego” dla jednego z nich, automatycznie znajdziesz „rozwiązanie problemu słownego” dla każdego „łatwego problemu wielokrotnego wyboru”!

Wreszcie problemy NP-zupełne to te, które są jednocześnie NP i NP-trudne. Zgodnie z naszą analogią są one jednocześnie „łatwe jak problemy wielokrotnego wyboru” i „najtrudniejsze ze wszystkich jako problemy słowne”.

Najprostszym z nich jest P, tutaj należy rozwiązać problemy rozwiązywane w czasie wielomianowym.

Potem nadchodzi NP. Należy tutaj rozwiązać problemy rozwiązywane w czasie wielomianowym na niedeterministycznej maszynie Turinga.

Twardość i kompletność muszą być redukowane. Problem A jest trudny dla klasy C, jeśli każdy problem w C zmniejsza się do A. Jeśli problem A jest trudny dla NP , lub NP-trudny, jeśli każdy problem w NP zmniejsza się do A.

Wreszcie problem jest kompletny dla klasy C, jeśli jest w C, a trudny dla C. W twoim przypadku problem A jest kompletny dla NP lub NP-zupełny, jeśli każdy problem w NP zmniejsza się do A, a A jest w NP .

Aby dodać do wyjaśnienia NP, problem występuje w NP wtedy i tylko wtedy, gdy rozwiązanie można zweryfikować w (deterministycznym) czasie wielomianowym. Zastanów się nad każdym znanym problemem NP-zupełnym, SAT, CLIQUE, SUBSET SUM, VERTEX COVER itp. Jeśli „uzyskasz rozwiązanie”, możesz zweryfikować jego poprawność w czasie wielomianowym. Są to, odpowiednio, przypisania prawdy do zmiennych, pełny podgraph, podzbiór liczb i zbiór wierzchołków, który dominuje na wszystkich krawędziach.

Dla Basic, P vs NP i złożoność obliczeniowa Zoo wideo wydaje się dużo łatwiejsze do zrozumienia.

W przypadku komputera z naprawdę dużą wersją problemu :

Problemy z P.

łatwy do rozwiązania (kostka rubix)

Problemy NP

trudne - ale sprawdzanie odpowiedzi jest łatwe (sudoku)

Być może są to naprawdę problemy z P, ale nie wiemy o tym ... P vs. NP .

Wiele problemów NP sprowadza się do tego samego (sudoku jest nowością na liście).

Problemy z EXP

naprawdę trudne (najlepszy następny ruch w szachy)

Trudne problemy z NP

Edycja: NP-twardy nie jest dobrze wyjaśniony na filmie (wszystkie różowe fragmenty), wykres NP-twardego Eulera w Wikipedii jest bardziej przejrzysty.

Podsumowanie wideo

Wikipedia NP-twardy schemat Eulera

P , NP , NP-zupełne i NP-twarde są klasami złożoności, klasyfikującymi problemy według złożoności algorytmicznej ich rozwiązywania. Krótko mówiąc, są one oparte na trzech właściwościach:

Rozwiązanie w czasie wielomianowym: Definiuje problemy decyzyjne, które mogą być rozwiązane przez deterministyczną maszynę Turinga (DTM) przy użyciu wielomianowej ilości czasu obliczeniowego, tj. Jego czas działania jest ograniczony górną granicą przez wyrażenie wielomianowe wielkości wejściowej dla algorytmu. Za pomocą notacji Big-O złożoność czasowa jest zdefiniowana jako O(n ^ k), gdzie n jest wielkością wejściowego współczynnika stałego ka.

Rozwiązanie weryfikowalne w czasie wielomianowym: Definiuje problemy decyzyjne, dla których dane rozwiązanie może być zweryfikowane przez DTM przy użyciu wielomianowej ilości czasu obliczeniowego, nawet jeśli uzyskanie poprawnego rozwiązania może wymagać dłuższego czasu.

Zmniejsza każdy problem NP w czasie wielomianowym : Definiuje problemy decyzyjne, których algorytmy do ich rozwiązania można wykorzystać do rozwiązania dowolnego problemu NP po kroku translacji czasu wielomianowego.

Niedawno napisałem artykuł na ten temat, podając więcej szczegółów, w tym demonstrację kodu w celu zredukowania problemu NP do problemu trudnego dla NP: Klasy złożoności problemów