pierwszą rzeczą do zrozumienia jest to, że P i np klasyfikują języki, a nie problemy. Aby zrozumieć, co to oznacza, potrzebujemy najpierw innych definicji.
alfabet jest niepustym skończonym zbiorem symboli.
{01} 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ę wyrazem nad Σ.
ciąg znaków101 jest słowem nad alfabetem {01}. Puste słowo (często pisane jako ε) jest słowem nad dowolnym alfabetem. Łańcuch penguin jest słowem nad alfabetem zawierającym znaki ASCII. Zapis dziesiętny liczby π nie jest słowem nad alfabetem {.0123456789} ponieważ nie jest skończona.
długość słowa w, zapisanego jako| w/, jest liczbą zawartych w nim symboli.
na przykład,/hello | = 5 i| ε / = 0. Dla dowolnego słowa w | / W / ∈ N i dlatego skończone.
niech Σ będzie alfabetem. Zbiór Σ＊ zawiera wszystkie wyrazy na Σ, w tym ε. Zbiór Σ + zawiera wszystkie wyrazy nad Σ, z wyłączeniem ε. Dla n ∈ N, Σn jest zbiorem słów o długości n.
dla każdego alfabetu Σ, Σ＊ i Σ+ są nieskończonymi zbiorami policzalnymi. Dla zbioru znaków ASCII ΣASCII wyrażenia regularne .* I .+ oznaczają odpowiednio ΣASCII＊ i ΣASCII+.
{01}7 to zestaw 7-bitowych kodów ASCII {00000000000001111111101}32 to zestaw 32-bitowych wartości całkowitych.
niech Σ będzie alfabetem i L&podzbiór; Σ＊. L nazywa się językiem nad Σ.
dla alfabetu Σ zbiór pusty i Σ＊ są językami trywialnymi nad Σ. Ten pierwszy jest często nazywany pustym językiem. Język pusty {} i język zawierający tylko puste słowo {ε} są różne.
podzbiór {01}32, który odpowiada innym niż Nan wartościom zmiennoprzecinkowym IEEE 754, jest językiem skończonym.
języki mogą mieć nieskończoną liczbę słów, ale każdy język jest policzalny. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Nieskończony zestaw ciągów {23571113, …} oznaczanie liczb pierwszych w notacji dziesiętnej jest ich właściwym podzbiorem. Język zawierający wszystkie słowa pasujące do wyrażenia regularnego ?\d+\.\d*(?\d+)? jest językiem nad zestawem znaków ASCII (oznaczającym podzbiór ważnych wyrażeń zmiennoprzecinkowych zdefiniowanych przez język programowania C).
nie ma języka zawierającego wszystkie liczby rzeczywiste (w żadnej notacji), ponieważ zbiór liczb rzeczywistych nie jest policzalny.
niech Σ będzie alfabetem i L&podzbiór; Σ＊. Maszyna d decyduje L, czy dla każdego wejścia w & w; Σ＊ oblicza funkcję charakterystyczną xL (w) w skończonym czasie. Funkcja charakterystyczna jest zdefiniowana jako
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.taka maszyna nazywa się decydentem dla L. piszemy „D (w) = x” dla „dane w, D wyjścia x”.
istnieje wiele modeli maszyn. Najbardziej ogólny, który jest obecnie w praktycznym użyciu, to model maszyny Turinga. Maszyna Turinga ma nieograniczone liniowe przechowywanie zgrupowane w komórki. Każda komórka może zawierać dokładnie jeden symbol alfabetu w dowolnym momencie. Maszyna Turinga wykonuje swoje obliczenia jako sekwencję kroków obliczeniowych. W każdym kroku może odczytać jedną komórkę, ewentualnie nadpisać jej wartość i przesunąć głowicę odczytu/zapisu o jedną pozycję w lewą lub prawą komórkę. To, co maszyna wykona, jest kontrolowane przez skończony automat stanu.
maszyna o dostępie swobodnym z skończonym zestawem instrukcji i nieograniczonym magazynowaniem to kolejny model maszyny, który jest tak potężny, jak model maszyny Turinga.
dla dobra tej dyskusji, nie będziemy zawracać sobie głowy dokładnym modelem maszyny, którego używamy, ale raczej wystarczy powiedzieć, że maszyna ma skończoną deterministyczną jednostkę sterującą, nieograniczoną pamięć masową i wykonuje obliczenia jako sekwencję kroków, które można policzyć.
ponieważ użył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 N0 ∈ N I c ∈ N takie, że dla każdego n ∈ N Z n > N0 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 i stałej 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 ↦ nk).
ponieważ O(N ↦ NK), choć matematycznie poprawne, jest niewygodne do pisania i czytania, większość ludzi – szczerze mówiąc, wszyscy poza mną – zwykle pisze po prostu O(nk).
zauważ, że granica zależy od długości w. Dlatego argument, który robisz dla języka liczb pierwszych jest poprawny tylko dla liczb w kodowaniu unaray, gdzie dla kodowania w liczby n Długość kodowania |w| jest proporcjonalna do N. nikt nigdy nie użyłby takiego kodowania w praktyce. Korzystając z bardziej zaawansowanego algorytmu, niż po prostu próbując 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 postaci binarnej (lub do dowolnej innej bazy). (Pomimo ogromnego zainteresowania, można to udowodnić tylko przez Manindra Agrawal, Neeraj Kayal i Nitin Saxena w nagradzanej pracy w 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 możesz napisać funkcje w swoim ulubionym języku programowania, które biorą łańcuch jako wejście i zwracają wartość logiczną informującą, czy łańcuch jest słowem z języka dla każdego z nich i udowodnić, że twoja funkcja ma wielomianową złożoność czasu pracy?
każdy język regularny (język opisany wyrażeniem regularnym) jest w P.
niech Σ będzie alfabetem i L&podzbiorem; Σ＊. 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.
- podane (w, c), V wychodzi 1 tylko wtedy, gdy w ∈ L.
- dla każdego w ∈ L istnieje c Σ Σ＊ takie, że V(W, c) = 1.
c w powyższej definicji nazywa się świadkiem (lub świadectwem).
weryfikator może dawać fałszywe negatywy niewłaściwemu świadkowi, nawet jeśli w rzeczywiście jest w L. nie wolno jednak dawać fałszywych pozytywów. Wymagane jest również, aby dla każdego słowa w języku istniał co najmniej jeden świadek.
dla języka złożonego, który zawiera kodowanie dziesiętne wszystkich liczb całkowitych, które nie są pierwsze, świadkiem może być Faktoryzacja. Na przykład (659, 709) jest świadkiem dla 467231 COMPOSITE COMPOSITE. Można to łatwo sprawdzić na kartce papieru, gdy bez świadka, udowodnienie, że 467231 nie jest prime byłoby trudne bez użycia komputera.
nie powiedzieliśmy nic o tym, jak można znaleźć odpowiedniego świadka. To jest 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 po krokach T (|w/) dla funkcji T ∈ O(n ↦ nk).
zauważ, że powyższa definicja zakłada, że dla każdego w ∈ L istnieje świadek c O |C| ≤ T(|w|). (Maszyna Turinga nie może patrzeć na więcej symboli świadka.)
NP to superset P (Dlaczego?). Nie wiadomo, czy istnieją języki, które są w NP, ale nie w P.
Faktoryzacja liczby całkowitej nie jest językiem per se. Możemy jednak skonstruować język, który reprezentuje związany z nim problem decyzyjny. Oznacza to, że język, który zawiera wszystkie krotki (n, m) takie, że n ma współczynnik D z d & leq; m. nazwijmy ten czynnik języka. Jeśli masz algorytm do decydowania o współczynniku, można go użyć do obliczenia pełnej faktoryzacji tylko z wielomianem narzutu, wykonując rekurencyjne wyszukiwanie binarne dla każdego czynnika pierwszego.
łatwo pokazać, że czynnik jest w NP. Odpowiednim świadkiem byłby po prostu sam czynnik d, A weryfikator musiałby tylko sprawdzić, czy 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, a to jest logarytmiczne w n.)
Jeśli możesz pokazać, że czynnik jest również w P, możesz być pewien, że otrzymasz wiele fajnych nagród. (I złamałeś znaczną część dzisiejszej kryptografii.)
dla każdego języka w NP istnieje algorytm brute-force, który decyduje o tym deterministycznie. Po prostu przeprowadza wyczerpujące poszukiwania wszystkich świadków. (Zauważ, że maksymalna długość świadka jest ograniczona wielomianem. Więc twój algorytm decydowania liczb pierwszych był algorytmem brutalnej siły decydowania liczb zespolonych.
aby odpowiedzieć na twoje ostatnie pytanie, musimy wprowadzić redukcję. Redukcje są bardzo potężnym pojęciem teoretycznej informatyki. Redukcja jednego problemu do drugiego w zasadzie oznacza rozwiązanie jednego problemu za pomocą rozwiązania innego problemu.
niech Σ będzie alfabetem, A A i B językami nad Σ. A jest wielomianem-czas wielu-jeden redukuje się do B, jeśli istnieje funkcja f: Σ＊ → Σ＊ o następujących właściwościach.
- W ∈ A ⇔ f(w) B 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 a ≤p B.
na przykład, Niech a będzie językiem, który zawiera wszystkie wykresy (zakodowane jako macierz adjacency) zawierające Trójkąt. (Trójkąt to cykl o długości 3.) Niech dalej B będzie językiem, który zawiera wszystkie macierze ze śladem niezerowym. (Ślad macierzy jest sumą jej głównych elementów przekątnych.) Wtedy A jest wielomianem-czas wielu-jeden redukuje się do B. Aby to udowodnić, musimy znaleźć odpowiednią funkcję transformacji f. w tym przypadku możemy ustawić f, aby obliczyć trzecią moc macierzy adjacency. Wymaga to dwóch iloczynów macierzy-macierzy, z których każdy ma złożoność wielomianową.
trywialnie prawdą jest, że L ≤p L. (można to udowodnić formalnie?)
zastosujemy to teraz do NP.
język L jest np-twardy wtedy i tylko wtedy, gdy L’ ≤P L dla każdego języka L’ ∈ NP.
język np-hard może, ale nie musi być w samym NP.
język L jest np-kompletny wtedy i tylko wtedy, gdy
- L ∈ NP i
- l jest np-twardy.
najbardziej znanym językiem NP jest SAT. Zawiera wszystkie formuły logiczne, które mogą być spełnione. Na przykład (A ∨ b) SAT (A ∨ b) SAT SAT. Ważnym świadkiem jest {a = 1, b = 0}. Formuła (A ∨ b) ∧ (A ∨ b) SAT B SAT SAT. (Jak byś to udowodnił?)
nietrudno pokazać, że SAT NP. Aby pokazać np-twardość SAT jest pewne dzieło, ale zostało to zrobione w 1971 roku przez Stephena Cooka.
gdy jeden język np-zupełny był znany, stosunkowo łatwo było pokazać np-zupełność innych języków poprzez redukcję. Jeśli język a jest znany jako np-twardy, to wykazanie, że a ≤p b pokazuje, że B jest również np-Twardy (poprzez przechodniość „≤p”). W 1972 Richard Karp opublikował listę 21 języków, które mógł wykazać jako np-kompletne poprzez (przechodnią) redukcję SAT. (Jest to jedyny artykuł w tej odpowiedzi, który faktycznie polecam przeczytać. W przeciwieństwie do innych, nie jest trudne do zrozumienia i daje bardzo dobry obraz tego, jak działa udowadnianie np-kompletności poprzez redukcję.)
wreszcie krótkie podsumowanie. Użyjemy symboli NPH i NPC do oznaczenia klas odpowiednio języków np-hard I np-complete.
- P& subseteq; NP
- NPC⊂ NP i NPC &podzbiór; NPH, właściwie NPC = np ∩ NPH z definicji
- (a ∈ NP) ∧ (B ∈ NPH) ≤a ≤ p b
zauważ, że włączenie NPC &podzbiór; NP jest właściwe nawet w przypadku, gdy P = NP. Aby to zobaczyć, wyjaśnij sobie, że żaden nietrywialny język nie może być zredukowany do trywialnego i istnieją trywialne języki w P, jak również nietrywialne języki w NP. Jest to jednak (niezbyt interesujący) przypadek narożny.
Twoim głównym źródłem zamieszania 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ę 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 użytego do wejścia.
w tym tygodniu został osiągnięty nowy rekord największej znanej Mersenne prime. Największą obecnie znaną liczbą pierwszą jest 274 207 281 − 1. Ta liczba jest tak ogromna, że przyprawia mnie o ból głowy, więc użyję mniejszej w poniższym przykładzie: 231 – 1 = 2 147 483 647. Może być zakodowany na różne sposoby.
- według wykładnika Mersenne ’ a jako liczby dziesiętnej:
31(2 bajty) - jako liczby dziesiętnej:
2147483647(10 bajtów) - jako liczby pojedynczej:
11111…11gdzie…ma zostać zastąpiony przez 2 147 483 640 więcej1s (prawie 2 GiB)
wszystkie te ciągi kodują tę samą liczbę i biorąc pod uwagę dowolny z nich, możemy łatwo skonstruować dowolne inne kodowanie tej samej liczby. (Możesz zastąpić kodowanie dziesiętne binarnym, ósemkowym lub szesnastkowym, jeśli chcesz. Zmienia tylko długość o stały współczynnik.)
naiwnym algorytmem do badania pierwotności jest tylko wielomian dla kodowania jednoargumentowego. Test pierwotności AKS jest wielomianem dla dziesiętnych (lub dowolnej innej zasady B ≥ 2). Test primalności Lucasa-Lehmera jest najbardziej znanym algorytmem dla liczb pierwszych Mersenne 'a Mp z P nieparzystą liczbą pierwszą, ale nadal jest wykładniczy w długości binarnego kodowania wykładnika Mersenne’ a p (wielomian w p).
Jeśli chcemy mówić o złożoności algorytmu, bardzo ważne jest, abyśmy byli bardzo jasni, 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. (Zauważ, że nie każda liczba pierwsza jest liczbą pierwszą Mersenne 'a, więc użycie wykładnika Mersenne’ a nie jest ogólnym schematem kodowania.)
w kryptografii teoretycznej wiele algorytmów formalnie przekazuje jako pierwszy parametr całkowicie bezużyteczny ciąg k 1 s. Algorytm nigdy nie patrzy na ten parametr, ale pozwala mu formalnie być wielomianem w k, który jest parametrem bezpieczeństwa używanym do regulacji bezpieczeństwa procedury.
w przypadku niektórych problemów, dla których językiem decyzyjnym w kodowaniu binarnym jest np-complete, język decyzyjny nie jest już np-complete, jeśli kodowanie liczb osadzonych jest zamienione na jednoargumentowe. Języki decyzyjne dla innych problemów pozostają NP-kompletne nawet wtedy. Te ostatnie nazywane są silnie np-complete. Najbardziej znanym przykładem jest pakowanie pojemników.
interesujące jest również (i być może bardziej) zobaczenie, jak zmienia się złożoność algorytmu, jeśli Dane wejściowe są skompresowane. Dla przykładu liczb pierwszych Mersenne ’ a widzieliśmy trzy kodowania, z których każdy jest logarytmicznie bardziej skompresowany niż jego poprzednik.
w 1983 roku Hana Galperin i Avi Wigderson napisali interesującą pracę na temat złożoności wspólnych algorytmów grafów, gdy kodowanie wejściowe grafu jest skompresowane logarytmicznie. Dla tych danych język grafów zawierających trójkąt z góry (gdzie był wyraźnie 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.