Pierwszą rzeczą do zrozumienia jest to, że P i NP klasyfikują języki , a nie problemy . Aby zrozumieć, co to oznacza, potrzebujemy najpierw kilku innych definicji.
Alfabet jest niepusty skończony zbiór symboli.
{ 0, 1} jest alfabetem, podobnie jak zestaw znaków ASCII. {} nie jest alfabetem, ponieważ jest pusty. N (liczby całkowite) nie jest alfabetem, ponieważ nie jest skończony.
Niech Σ będzie alfabetem. Uporządkowana konkatenacja skończonej liczby symboli z Σ nazywa się słowem nad Σ .
Ciąg 101jest słowem nad alfabetem { 0, 1}. Pustym słowem (często zapisywane jako ε ) to słowo w dowolnym alfabecie. Ciąg penguinjest słowem nad alfabetem zawierającym znaki ASCII. Zapis dziesiętny z liczby Õ nie jest słowo nad alfabetem { ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, ponieważ nie jest skończony.
Długość wyrazu wag , napisany jako | w |, jest w nim liczbą symboli.
Na przykład | hello| = 5 i | ε | = 0. Dla dowolnego słowa w , | w | ∈ N, a zatem skończony.
Niech Σ będzie alfabetem. Zestaw Σ ＊ zawiera wszystkie słowa nad Σ , w tym ε . Zbiór Σ + zawiera wszystkie słowa nad Σ , z wyjątkiem ε . Dla n ∈ N , Σ n jest zbiorem słów o długości n .
Dla każdego alfabetu Σ , Σ ＊ i Σ + są nieskończonymi policzalnymi zestawami . Dla znaków ASCII zestaw Ď ASCII , wyrażeń regularnych .*i .+oznaczają Ď ASCII * i Ď ASCII + odpowiednio.
{ 0, 1} 7 to zestaw 7-bitowe kody ASCII { 0000000, 0000001..., 1111111}. { 0, 1} 32 to zbiór 32-bitowych liczb całkowitych.
Niech Σ będzie alfabetem, a L ⊆ Σ ＊ . L nazywa się językiem ponad Σ .
W przypadku alfabetu Σ pusty zestaw i Σ ＊ są trywialnymi językami ponad Σ . Ten pierwszy jest często określany jako pusty język . Pusty język {} i język zawierający tylko puste słowo { ε } są różne.
Podzbiór { 0, 1} 32, który odpowiada wartościom zmiennoprzecinkowym innym niż NaN IEEE 754, jest językiem skończonym.
Języki mogą zawierać nieskończoną liczbę słów, ale każdy język jest policzalny. Zbiór ciągów { 1, 2...} oznaczających liczby całkowite w notacji dziesiętnej jest nieskończona język nad alfabetem { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Nieskończony zbiór ciągów { 2, 3, 5, 7, 11, 13, ...} oznaczający liczb pierwszych w notacji dziesiętnej jest jego podzbiorem właściwym. Językiem zawierającym wszystkie słowa pasujące do wyrażenia regularnego [+-]?\d+\.\d*([eE][+-]?\d+)?jest język nad zestawem znaków ASCII (oznaczającym podzbiór prawidłowych wyrażeń zmiennoprzecinkowych zdefiniowanych przez język programowania C).
Nie ma języka zawierającego wszystkie liczby rzeczywiste (w dowolnej notacji), ponieważ zestawu liczb rzeczywistych nie można policzyć.
Niech Σ będzie alfabetem, a L ⊆ Σ ＊ . Maszyna D decyduje L, jeśli dla każdego wejścia w ∈ Σ ＊ oblicza funkcję charakterystyczną χ L ( w ) w skończonym czasie. Funkcja charakterystyczna jest zdefiniowana jako
χ L : Σ ＊ → {0, 1}
w ↦ 1, w ∈ L
0, w przeciwnym razie.
Taka maszyna nazywa się decydującym dla L . Piszemy „ D ( w ) = x ” dla „danych w , D wyjść x ”.
Istnieje wiele modeli maszyn. Najbardziej ogólnym, który jest dzisiaj w praktyce, jest model maszyny Turinga . Maszyna Turinga ma nieograniczoną pamięć liniową zgrupowaną w komórki. Każda komórka może przechowywać dokładnie jeden symbol alfabetu w dowolnym momencie. Maszyna Turinga wykonuje obliczenia jako sekwencję kroków obliczeniowych. Na każdym etapie może odczytać jedną komórkę, ewentualnie zastąpić jej wartość i przesunąć głowicę odczytu / zapisu o jedną pozycję do lewej lub prawej komórki. Działanie, jakie wykona maszyna, jest kontrolowane przez automat skończony.
Maszyna o swobodnym dostępie ze skończonym zestawem instrukcji i nieograniczonym miejscem do przechowywania to kolejny model maszyny, który jest równie potężny jak model maszyny Turinga.
Ze względu na tę dyskusję nie będziemy zawracać sobie głowy precyzyjnym modelem maszyny, którego używamy, ale wystarczy powiedzieć, że maszyna ma skończoną deterministyczną jednostkę sterującą, nieograniczoną pamięć i wykonuje obliczenia jako sekwencję kroków, które można policzyć.
Ponieważ używałeś go w swoim pytaniu, zakładam, że znasz już notację „big-O”, więc tutaj jest tylko szybkie odświeżenie.
Niech f : N → będzie funkcją. Zbiór O ( f ) zawiera wszystkie funkcje g : N → N, dla których istnieją stałe n 0 ∈ N i c ∈ N takie, że dla każdego n ∈ N przy n > n 0 prawdą jest, że g ( n ) ≤ c f ( n ).
Teraz jesteśmy gotowi podejść do prawdziwego pytania.
Klasa P zawiera wszystkie języki L, dla których istnieje maszyna Turinga D, która decyduje o L, oraz stałą k ∈ N taką, że dla każdego wejścia w , D zatrzymuje się co najwyżej po krokach T (| w |) dla funkcji T ∈ O ( n ↦ n k ).
Ponieważ O ( n ↦ n k ), choć poprawne matematycznie, jest niewygodne w pisaniu i czytaniu, większość ludzi - szczerze mówiąc, wszyscy oprócz mnie - zwykle pisze po prostu O ( n k ).
Zauważ, że granica zależy od długości w . Dlatego argument, który wysunąłeś za język liczb pierwszych, jest poprawny tylko dla liczb w kodowaniach nieregularnych , gdzie dla kodowania w liczby n , długość kodowania | w | jest proporcjonalny do n . Nikt nigdy nie używałby takiego kodowania w praktyce. Używając bardziej zaawansowanego algorytmu niż po prostu wypróbowanie wszystkich możliwych czynników, można jednak wykazać, że język liczb pierwszych pozostaje w P, jeśli dane wejściowe są zakodowane w systemie binarnym (lub w dowolnej innej bazie). (Pomimo ogromnego zainteresowania, może to udowodnić tylko Manindra Agrawal, Neeraj Kayal i Nitin Saxena w wielokrotnie nagradzanym artykule z 2004 roku, więc można się domyślić, że algorytm nie jest bardzo prosty.)
Trywialne języki {} i Σ ＊ oraz nietrywialny język { ε } są oczywiście w P (dla dowolnego alfabetu Σ ). Czy potrafisz pisać funkcje w swoim ulubionym języku programowania, które przyjmują ciąg znaków jako dane wejściowe i zwracają wartość logiczną informującą, czy ciąg jest słowem z języka dla każdego z nich i dowodzą, że twoja funkcja ma wielomianową złożoność w czasie wykonywania?
Każdy regularny język (język opisane przez wyrażenie regularne) jest P .
Niech Σ będzie alfabetem, a L ⊆ Σ ＊ . Maszyna V, która przyjmuje zakodowaną krotkę dwóch słów w , c ∈ Σ ＊ i wyprowadza 0 lub 1 po skończonej liczbie kroków, jest weryfikatorem dla L, jeśli ma następujące właściwości.
- Biorąc pod uwagę, ( W , c ), V, wyjściowe 1 tylko wtedy, gdy w ∈ L .
- Dla każdego w ∈ L istnieje c ∈ Σ ＊ takie, że V ( w , c ) = 1.
Litera c w powyższej definicji nazywa się świadkiem (lub zaświadczeniem ).
Weryfikator może dać fałszywie ujemne dla niewłaściwego świadka, nawet jeśli w rzeczywistości jest w L . Nie wolno jednak podawać fałszywych wyników pozytywnych. Wymagane jest również, aby dla każdego słowa w języku istniał co najmniej jeden świadek.
Dla języka KOMPOZYTOWEGO, który zawiera kodowanie dziesiętne wszystkich liczb całkowitych, które nie są liczbami pierwszymi, świadek może być faktoryzacją. Na przykład (659, 709)jest świadkiem 467231∈ KOMPOZYTU. Można to łatwo zweryfikować na kartce papieru bez podania świadka, dowodzenie, że 467231 nie jest liczbą pierwszą, byłoby trudne bez użycia komputera.
Nie mówiliśmy nic o tym, jak znaleźć odpowiedniego świadka. To część niedeterministyczna.
Klasa NP zawiera wszystkie języki L, dla których istnieje maszyna Turinga V, która weryfikuje L i stałą k ∈ N taką, że dla każdego wejścia ( w , c ) V zatrzymuje się co najwyżej T (| w |) kroków dla funkcji T ∈ O ( n ↦ n k ).
Zauważ, że powyższa definicja implikuje, że dla każdego w ∈ L istnieje świadek cz | c | ≤ T (| w |). (Maszyna Turinga nie jest w stanie spojrzeć na więcej symboli świadka.)
NP jest nadzbiorem P (dlaczego?). Nie wiadomo, czy istnieją języki, które są w NP , ale nie w P .
Rozkład na czynniki całkowite nie jest językiem per se. Możemy jednak zbudować język, który reprezentuje związany z nim problem decyzyjny . Oznacza to, że język, który zawiera wszystkie krotki ( n , m ), że n ma współczynnik d z d ≤ m . Nazwijmy ten język FACTOR. Jeśli masz algorytm decydujący o CZYNNIKU, możesz go użyć do obliczenia pełnego faktoryzacji z tylko narzutem wielomianowym, wykonując rekurencyjne wyszukiwanie binarne dla każdego czynnika pierwszego.
Łatwo jest wykazać, że FACTOR jest w NP . Odpowiednie świadectwo byłoby po prostu czynnik d sama i wszystko weryfikator musiałby zrobić, to sprawdzić, d ≤ m i n mod d = 0. Wszystko to można zrobić w czasie wielomianowym. (Pamiętaj jeszcze raz, że liczy się długość kodowania i jest ona logarytmiczna w n .)
Jeśli potrafisz pokazać, że WSPÓŁCZYNNIK jest również w P , możesz być pewien, że dostaniesz wiele fajnych nagród. (I złamałeś znaczną część dzisiejszej kryptografii.)
Dla każdego języka w NP istnieje algorytm brutalnej siły, który decyduje o nim deterministycznie. Po prostu przeprowadza wyczerpujące przeszukanie wszystkich świadków. (Zauważ, że maksymalna długość świadka jest ograniczona wielomianem.) Tak więc, twój algorytm do decydowania o PRIMES był w rzeczywistości algorytmem brutalnej siły do decydowania o KOMPOZYTIE.
Aby odpowiedzieć na twoje ostatnie pytanie, musimy wprowadzić redukcję . Redukcje są bardzo potężną koncepcją informatyki teoretycznej. Zmniejszenie jednego problemu do drugiego w zasadzie oznacza rozwiązanie jednego problemu przez rozwiązanie innego problemu.
Niech Σ będzie alfabetem, a A i B będą językami ponad Σ . A jest wielomianem wielokrotnym jeden redukowanym do B, jeśli istnieje funkcja f : Σ ＊ → Σ ＊ o następujących właściwościach.
- w ∈ A ⇔ f ( w ) ∈ B dla wszystkich w ∈ Σ ＊ .
- Funkcja f może być obliczona przez maszynę Turinga dla każdego wejścia w w kilku krokach ograniczonych wielomianem w | w |.
W tym przypadku piszemy ≤ p B .
Na przykład niech A będzie językiem, który zawiera wszystkie wykresy (zakodowane jako macierz przylegania), które zawierają trójkąt. (Trójkąt jest cyklem długości 3.) Niech dalszy B będzie językiem, który zawiera wszystkie macierze o niezerowym śladzie. (Ślady matrycy jest sumą jego głównych elementów diagonalnych). Następnie jest wielomianem czasie wielu jeden zredukować do B . Aby to udowodnić, musimy znaleźć odpowiednią funkcję transformacji f . W takim przypadku możemy ustawić f, aby obliczyć trzecią moc macierzy przyległości. Wymaga to dwóch produktów matrycowo-matrycowych, z których każdy ma złożoność wielomianową.
To prawda, że jest trywialnie L ≤ p L . (Czy możesz to formalnie udowodnić?)
Zastosujemy to teraz do NP .
Językiem L jest NP - twardy wtedy i tylko wtedy, gdy L '≤ p L dla każdego języka L ' ∈ NP .
An NP język -hard mogą lub nie mogą być w NP samego.
Język L jest NP- kompletny wtedy i tylko wtedy, gdy
- L ∈ NP i
- L oznacza NP- twardy.
Najbardziej znanym językiem z kompletnym NP jest SAT. Zawiera wszystkie formuły logiczne, które można spełnić. Na przykład ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Prawidłowym świadkiem jest { a = 1, b = 0}. Wzór ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Jak byś to udowodnił?)
Nie jest trudno wykazać, że SAT ∈ NP . Aby pokazać NP -hardness z SAT jest trochę pracy, ale to było zrobione w 1971 roku przez Stephena Cooka .
Gdy znany był jeden język NP-zupełny , względnie proste było wykazanie kompletności NP innych języków poprzez redukcję. Jeśli wiadomo , że język A jest twardy NP , to pokazanie, że A ≤ p B pokazuje, że B jest również twardy NP (poprzez przechodniość „≤ p ”). W 1972 r. Richard Karp opublikował listę 21 języków, które mógł pokazać jako NP-kompletne poprzez (przechodnie) redukcję SAT. (Jest to jedyny artykuł w tej odpowiedzi, który naprawdę polecam przeczytać. W przeciwieństwie do innych, nie jest trudny do zrozumienia i daje bardzo dobre wyobrażenie o tym, jak działa sprawdzanie kompletności NP poprzez redukcję.)
Wreszcie krótkie podsumowanie. Użyjemy symboli NPH i NPC, aby oznaczyć klasy odpowiednio języków NP- twardych i NP- kompletnych.
- P ⊆ NP
- NPC ⊂ NP i NPC ⊂ NPH , faktycznie NPC = NP ∩ NPH z definicji
- ( A ∈ NP ) ∧ ( B ∈ NPH ) ⇒ A ≤ p B
Zauważ, że włączenie NPC ⊂ NP jest właściwe nawet w przypadku, gdy P = NP . Aby to zobaczyć, wyjaśnij, że żaden nie-trywialny język nie może zostać zredukowany do trywialnego, a istnieją trywialne języki w P, a także nietrywialne w NP . Jest to jednak (niezbyt interesujący) przypadek narożny.
Uzupełnienie
Głównym źródłem nieporozumień wydaje się być to, że myślałeś o „ n ” w „ O ( n ↦ f ( n ))” jako interpretacji danych wejściowych algorytmu, gdy faktycznie odnosi się ono do długości danych wejściowych. Jest to ważne rozróżnienie, ponieważ oznacza, że asymptotyczna złożoność algorytmu zależy od kodowania zastosowanego na wejściu.
W tym tygodniu osiągnięto nowy rekord największej znanej liczby pierwszej Mersenne . Największa znana obecnie liczba pierwsza to 2 74 207 281 - 1. Liczba ta jest tak ogromna, że sprawia mi ból głowy, więc użyję mniejszej w poniższym przykładzie: 2 31 - 1 = 2 147 483 647. Może być zakodowane na różne sposoby.
- przez wykładnik Mersenne jako liczba dziesiętna:
31(2 bajty)
- jako liczba dziesiętna:
2147483647(10 bajtów)
- jako liczba jednoznaczna:
11111…11gdzie …należy zastąpić 2 147 483 640 więcej 1s (prawie 2 GiB)
Wszystkie te ciągi kodują ten sam numer, a biorąc pod uwagę dowolny z nich, możemy łatwo skonstruować dowolne inne kodowanie tego samego numeru. (Jeśli chcesz, możesz zastąpić kodowanie dziesiętne cyframi binarnymi, ósemkowymi lub szesnastkowymi. Zmienia to jedynie stały współczynnik).
Naiwny algorytm testowania pierwotności jest wielomianem tylko w przypadku kodowania jednoargumentowego. Test AKS pierwszości jest wielomianem do dziesiętną (lub innej podstawy b ≥ 2). Test Lucasa-Lehmera jest najlepiej znany algorytm Liczby Mersenne'a M s o p nieparzystą liczbę pierwszą ale nadal jest wykładnicza o długości binarnego kodowania Mersenne wykładnik P (wielomian P ).
Jeśli chcemy porozmawiać o złożoności algorytmu, bardzo ważne jest, abyśmy byli bardzo pewni, jakiej reprezentacji używamy. Ogólnie można założyć, że stosowane jest najbardziej wydajne kodowanie. Oznacza to, że binarne dla liczb całkowitych. (Pamiętaj, że nie każda liczba pierwsza jest liczbą pierwszą Mersenne, więc użycie wykładnika Mersenne nie jest ogólnym schematem kodowania).
W kryptografii teoretycznej wiele algorytmów jest formalnie przekazywanych jako całkowicie niepotrzebny ciąg ks 1 jako pierwszy parametr. Algorytm nigdy nie patrzy na ten parametr, ale pozwala mu formalnie być wielomianem w k , który jest parametrem bezpieczeństwa używanym do dostrajania bezpieczeństwa procedury.
W przypadku niektórych problemów, dla których językiem decyzyjnym w kodowaniu binarnym jest NP-zupełny , język decyzyjny nie jest już NP-zupełny, jeśli kodowanie liczb osadzonych zostanie przełączone na jednoargumentowy. Języki decyzyjne dotyczące innych problemów pozostaje NP -Complete nawet wtedy. Te ostatnie nazywane są silnie NP -kompletnymi . Najbardziej znanym przykładem jest pakowanie pojemników .
Interesujące jest również (i być może bardziej) obserwowanie, jak zmienia się złożoność algorytmu, jeśli dane wejściowe zostaną skompresowane . Na przykład liczb pierwszych Mersenne'a widzieliśmy trzy kodowania, z których każde jest logarytmicznie bardziej skompresowane niż jego poprzednik.
W 1983 r. Hana Galperin i Avi Wigderson napisali interesujący artykuł na temat złożoności popularnych algorytmów grafowych, gdy kodowanie wejściowe wykresu jest kompresowane logarytmicznie. Dla tych danych wejściowych język wykresów zawierających trójkąt z góry (gdzie wyraźnie było to w P ) nagle staje się NP-zupełny .
A to dlatego, że klasy językowe takie jak P i NP są zdefiniowane dla języków , a nie dla problemów .
