Zasadniczo masz rację co do P i NP, ale nie co do NP-trudnych i NP-zakończonych.

Na początek oto super-zwięzłe definicje czterech omawianych klas złożoności:

• P to klasa problemów decyzyjnych, które mogą być rozwiązane w czasie wielomianowym przez deterministyczną maszynę Turinga.

• NP to klasa problemów decyzyjnych, które mogą być rozwiązane w czasie wielomianowym przez niedeterministyczną maszynę Turinga. Równocześnie jest to klasa problemów, które mogą być weryfikowane w czasie wielomianowym przez deterministyczną maszynę Turinga.

• NP-trudne to klasa problemów decyzyjnych, do których wszystkie problemy w NP zredukowana do czasu wielomianowego przez deterministyczną maszynę Turinga.

• NP-zupełne jest przecięciem NP-twardy i NP. Równoważnie, NP-zupełne jest klasą problemów decyzyjnych w NP, do której wszystkie inne problemy w NP można zredukować w czasie wielomianowym przez deterministyczną maszynę Turinga.

I tutaj „Schemat sa Eulera z Wikipedii pokazujący relacje między tymi czterema klasami (zakładając, że P nie jest równe NP):

Część, którą zakładam, że „najbardziej nie znasz lub mylisz jest pojęciem „wielomianowej redukcji czasu” od problemu X do problemu Y. Redukcja z X do Y jest po prostu algorytmem A, który rozwiązuje X poprzez użycie innego algorytmu B, który rozwiązuje problem Y. Ta redukcja nazywa się a ” redukcja czasu wielomianu „, jeżeli wszystkie części A inne niż B mają wielomianową złożoność czasową. Jako trywialny przykład, problem znalezienia najmniejszego elementu w tablicy jest sprowadzany w czasie stałym do problemu sortowania, ponieważ można posortować tablicę, a następnie zwrócić pierwszy element posortowanej tablicy.

Jeden rzeczą, której łatwo przeoczyć w definicji NP-trudnej jest to, że redukcja przechodzi od problemów NP do problemu NP-trudnego, ale niekoniecznie odwrotnie . Oznacza to, że problemy NP-trudne mogą być w NP lub w znacznie wyższej klasie złożoności (jak widać na diagramie Eulera), lub mogą nawet nie być problemami rozstrzygalnymi.Dlatego ludzie często mówią coś w stylu „NP-trudne oznacza co najmniej tak trudne jak NP”, gdy próbują wyjaśnić te rzeczy nieformalnie.

Problem z zatrzymaniem jest dobrym przykładem problemu NP-trudnego, który „najwyraźniej nie jest w NP, ponieważ Wikipedia wyjaśnia :

Łatwo jest udowodnić, że problem zakończenia pracy jest NP-trudny, ale nie jest NP-całkowity. Na przykład problem spełnialności logicznej można sprowadzić do problemu zatrzymania, przekształcając go w opis maszyny Turinga, która próbuje przypisać wszystkie wartości prawdy, a gdy znajdzie taką, która spełnia formułę, zatrzymuje się, a w przeciwnym razie przechodzi w nieskończoną pętlę. Łatwo też zauważyć, że problem zatrzymania nie występuje w NP, ponieważ wszystkie problemy w NP są rozstrzygalne w skończonej liczbie operacji, podczas gdy problem zatrzymania jest ogólnie nierozstrzygalny.

Komentarze

• @Nakano Intuicyjnie, ' sa ” redukcja ” w tym sensie, że jeden problem staje się podproblem innego problemu. Fakt, że niektóre z tych redukcji zwiększają złożoność, zamiast ją zmniejszać przez zły wybór ” podproblemu „, oznacza po prostu, że nigdy nie użyjesz tych redukcji w dowolnym kodzie świata rzeczywistego. Chociaż szczerze mówiąc NP-hard wydaje mi się dziwną i niezbyt interesującą klasą; bardziej owocne może być zignorowanie tego i pomyślenie o NP-complete jako zestawie problemów NP, do których redukują się wszystkie inne problemy NP.
• @Nakano stackoverflow.com/questions/12637582/… Myślę, że krótka odpowiedź jest taka, że kiedy ludzie mówią o faktoryzacji liczb całkowitych jako NP, ' normalnie mówimy o naprawdę dużych liczbach całkowitych, dla których generalnie zaczynasz sprawdzać duże-O z n jako ” liczbą bitów, które liczba całkowita zajmuje w pamięci ” zamiast ” liczbę liczb całkowitych przekazanych do funkcji „.
• @Nakano: W notacji duże-O n jest miarą rozmiaru wejścia (liczby elementów, bajtów, cyfr itp.), A nie wartości .
• @Nakano Krótka odpowiedź jest taka, że ' wszystko w porządku i dlatego podczas wspólnego Analiza złożoności zawsze musisz określić, co oznacza n . Twierdzenie, że n jest ” rozmiarem danych wejściowych „, jest jedynie zwięzłym podsumowaniem tego, jak zwykle definiujemy n. To ' nie jest częścią rygorystycznych definicji notacji duże-O ani złożoności czasowej. Uważam, że masz rację, mówiąc, że rozkład na czynniki całkowite wynosi O (sqrt (n)), gdy n jest wartością danych wejściowych. Tak się składa, że wyniki złożoności, w których n oznacza rozmiar, są zwykle o wiele bardziej przydatne w praktyce niż te, w których n oznacza wartość.
• @Nakano It ' Warto również pamiętać, że technicznie musisz również zdefiniować złożoność czasową swoich prymitywnych operacji (dodawanie, mnożenie, czytanie z pamięci, zapisywanie do pamięci, porównywanie dwóch liczb). W większości przypadków zakładamy, że wszystkie te prymitywy są stałe lub liczymy tylko jeden rodzaj operacji (np. W przypadku algorytmów sortowania tradycyjnie liczymy porównania). Podejrzewam, że wyniki rozkładu liczb całkowitych nie ' nie zakładają, że wszystkie te operacje mają stały czas, tak jak zwykle, w przeciwnym razie rozmiar liczby nie ' nie ma wielkiego znaczenia.

Rozkład na czynniki całkowite jest cytowany jako przykład NP, ale osobiście nie rozumiem, dlaczego to nie jest P, ponieważ rozkład próbny zajmuje O (sqrt (n)) czasu.

Dla celów klas złożoności n jest długością wejścia. Więc jeśli chcesz wziąć pod uwagę liczbę całkowitą k, n to nie k, ale log k, liczba bitów (lub cokolwiek) potrzebna do zapisania liczby. Tak więc rozkładanie na czynniki całkowite to O(sqrt(k)), jak mówisz, ale to jest O(sqrt(2n)), czyli O(2(n/2)).

Zakładam, że NP-Hard jest po prostu pełen niewiadomych. Trudne do zweryfikowania, trudne do rozwiązania.

Nie. NP-Hard to po prostu to, jak trudny jest problem do rozwiązania.

Problemy NP-Hard są co najmniej tak trudne, jak najtrudniejszy problem w NP. Wiemy, że są co najmniej tak trudne, ponieważ gdybyśmy mieli algorytm czasu wielomianowego dla problemu NP-trudnego, moglibyśmy dostosować ten algorytm do dowolnego problemu w NP.

NP-Complete W ogóle nie rozumiem

NP- Kompletny oznacza, że problem jest zarówno NP, jak i NP-trudny. Oznacza to, że możemy szybko zweryfikować rozwiązanie (NP), ale jest ono co najmniej tak trudne, jak najtrudniejszy problem w NP (NP-trudny).

Naprawdę nie wiem, co to znaczy być niedeterministycznym.

Non -determinizm jest alternatywną definicją NP. Niedeterministyczna maszyna Turinga jest w stanie skutecznie powielić się w dowolnym momencie i kazać każdemu duplikatowi wybrać inną ścieżkę wykonania. Zgodnie z tą definicją NP jest zbiorem problemów, które mogą być rozwiązane w czasie wielomianowym przez komputer, który może swobodnie się powielać. Okazuje się, że jest to dokładnie ten sam zestaw problemów, które można zweryfikować w czasie wielomianowym.

Komentarze

• Tak więc jest to możliwe dla $ O ( n ^ k) Algorytmy $ time mają być problemami NP?
• k jest stałą liczbą rzeczywistą? Tak. Wszystkie problemy P są również problemami NP. Oczywiście wszystko, co można rozwiązać w czasie wielomianowym, można również zweryfikować w czasie wielomianowym.
• Jak właściwie definiuje się tutaj długość / rozmiar? Na przykład mógłbym po prostu napisać $ n $ w dużej podstawie i zmniejszyć jego długość podczas pisania. A co z problemami, które nie ' nie dotyczą bezpośrednio liczb całkowitych, ale powiedzmy, że wykresy mają wierzchołki $ V $ i krawędzie $ E $ itd.
• @Nakano, właściwie duża podstawa nie ' nie zmieniłaby tego, ponieważ byłaby to tylko stała różnica współczynnika. Więc nie ' nie wpłynie na wielomian vs nie wielomian. Jeśli jednak wpiszesz liczbę w jednoargumentowym, to zmieni to.
• @Nakano, hmm … Nie ' nie odważyłbym się wyjaśnić złożoności zajęcia do piątego roku życia. : P

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 to niepusty, skończony zbiór symboli.

{0 , 1} to alfabet, podobnie jak zestaw znaków ASCII. {} nie jest alfabetem, ponieważ jest pusty. N (liczby całkowite) nie jest alfabetem, ponieważ nie jest skończone.

Niech Σ bądź alfabetem. Uporządkowana konkatenacja skończonej liczby symboli z Σ jest nazywana słowem ponad Σ .

Ciąg 101 to słowo nad alfabetem {0, 1}. puste słowo (często zapisywane jako ε ) to słowo nad dowolnym alfabetem. Ciąg penguin to słowo nad alfabetem zawierające znaki ASCII. Zapis dziesiętny liczby π nie jest słowem nad alfabetem {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, ponieważ nie jest skończone.

długość słowa w , zapisane jako | w |, to liczba symboli w nim.

Na przykład | hello | = 5 i | ε | = 0. Dla dowolnego słowa w , | w | ∈ N , a zatem skończone.

Niech Σ być alfabetem. Zestaw Σ ^＊ zawiera wszystkie słowa powyżej Σ , w tym ε . Zestaw Σ ⁺ zawiera wszystkie słowa powyżej Σ , z wyłączeniem ε . Dla n ∈ N , Σ ⁿ to zbiór słów o długości n .

Dla każdy alfabet Σ , Σ ^＊ i Σ ⁺ są nieskończone policzalne zestawy .W przypadku zestawu znaków ASCII Σ _ASCII , wyrażenia regularne .* i .+ oznacz Σ _ASCII ^＊ i Σ _ASCII ⁺ odpowiednio.

{0, 1} ⁷ to zestaw 7-bitowych kodów ASCII {0000000, 0000001,…, 1111111}. {0, 1} ³² to zbiór 32-bitowych liczb całkowitych.

Niech Σ będzie alfabetem, a L ⊆ Σ ^＊ . L jest nazywany językiem w porównaniu z Σ .

W przypadku alfabetu Σ pusty zestaw i Σ ^＊ to trywialne języki w porównaniu z Σ . Ten pierwszy jest często nazywany pustym językiem . Pusty język {} i język zawierający tylko puste słowo { ε } są różne.

Podzbiór {0, 1} ³² , który odpowiada wartościom zmiennoprzecinkowym innym niż NaN IEEE 754, jest językiem skończonym.

Języki mogą mieć 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 to nieskończony 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ące liczby pierwsze w notacji dziesiętnej jest ich odpowiednim podzbiorem. Język zawierający wszystkie słowa pasujące do wyrażenia regularnego [+-]?\d+\.\d*([eE][+-]?\d+)? jest językiem opartym na zestawie znaków ASCII (oznaczającym podzbiór prawidłowych wyrażeń zmiennoprzecinkowych zgodnie z definicją w języku programowania C).

Nie ma języka zawierającego wszystkie liczby rzeczywiste (w dowolnej notacji), ponieważ zbioru liczb rzeczywistych nie da się policzyć.

Niech Σ bądź alfabetem i L ⊆ Σ ^＊ . Maszyna D decyduje L jeśli dla każdego wejścia w ∈ Σ ^＊ oblicza funkcję charakterystyczną χ _L ( w ) w skończonym czasie. Charakterystyczna funkcja jest zdefiniowana jako

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Taka maszyna jest nazywana decider dla L . Piszemy „ D ( w ) = x ” dla „danego w , D wyjścia x ”.

Istnieje wiele modeli maszyn. Najbardziej ogólnym, obecnie używanym w praktyce, jest model maszyny Turinga . Maszyna Turinga ma nieograniczoną pamięć liniową skupioną w komórkach. Każda komórka może w dowolnym momencie zawierać dokładnie jeden symbol alfabetu. Maszyna Turinga wykonuje 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ę do lewej lub prawej komórki. To, jakie działanie wykona maszyna, jest kontrolowane przez automat skończony.

Maszyna o swobodnym dostępie z skończonym zestawem instrukcji i nieograniczoną pamięcią masową to kolejny model maszyny, który jest równie potężny jak model maszyny Turinga.

Na potrzeby tej dyskusji nie będziemy zawracać nam głowy dokładnym 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żyłeś go w swoim pytaniu, zakładam, że znasz już notację „duże-O” więc tutaj jest tylko krótkie przypomnienie.

Niech f : N → być funkcją.Zestaw O ( f ) zawiera wszystkie funkcje g : N → N , dla którego istnieją stałe n ₀ ∈ N i c ∈ N takie, że dla każdego n ∈ N z n > n ₀ it jest prawdą, ż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 L i stałą k ∈ N taką, że dla każdego wejścia w , D zatrzymuje się po co najwyżej T (| w |) krokach dla funkcji T ∈ O ( n ↦ n ^k ).

Od O ( n ↦ n ^k ), chociaż matematycznie poprawne, jest niewygodne w pisaniu i czytaniu, większość ludzi – szczerze mówiąc, wszyscy oprócz mnie – zwykle pisze po prostu O(n^k ).

Pamiętaj, że ograniczenie zależy od długości w . Dlatego argument, który podajesz za język liczb pierwszych, jest poprawny tylko dla liczb w kodowaniach niejednoznacznych , gdzie dla kodowania w z liczba n , długość kodowania | w | jest proporcjonalne do n . W praktyce nikt nigdy nie użyłby takiego kodowania. Korzystając z bardziej zaawansowanego algorytmu niż po prostu wypróbowując wszystkie możliwe czynniki, można jednak wykazać, że język liczb pierwszych pozostaje w P , jeśli dane wejściowe są kodowane binarnie (lub na inną podstawę). (Pomimo ogromnego zainteresowania, można to udowodnić jedynie w nagrodzonym artykule z 2004 roku Manindrze Agrawal, Neeraj Kayal i Nitin Saxena , więc można się domyślić, że algorytm nie jest bardzo prosty.)

Tryskające języki {} i Σ ^＊ i nietrywialny język { ε } są oczywiście w P (dla dowolnego alfabetu Σ ). Czy możesz napisać 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 dany ciąg jest słowem z języka dla każdego z nich, i udowodnić, że funkcja ma wielomianową złożoność w czasie wykonywania? p> Każdy regularny język (język opisany wyrażeniem regularnym) znajduje się w P .

Niech Σ będzie alfabetem, a L ⊆ Σ ^＊ . Maszyna V , która przyjmuje zakodowaną krotkę dwóch słów w , c ∈ Σ ^＊ i wyświetla 0 lub 1 po skończonej liczbie kroków jako weryfikator dla L , jeśli ma następujące właściwości.

• Podane ( w , c ), V zwraca 1 tylko wtedy, gdy w ∈ L .
• Dla każdego w ∈ L tam istnieje c ∈ Σ ^＊ taki, że V ( w , c ) = 1.

c w powyższej definicji to świadek (lub certyfikat ) .

Weryfikator może podać fałszywie negatywy dla niewłaściwego świadka, nawet jeśli w faktycznie znajduje się w L . Nie wolno jednak podawać fałszywych alarmów. Wymagane jest również, aby dla każdego słowa w języku istniał co najmniej jeden świadek.

W przypadku języka COMPOSITE, który zawiera kodowanie dziesiętne wszystkich liczb całkowitych, które nie są liczbą pierwszą , świadek może być faktoryzacją. Na przykład (659, 709) jest świadkiem 467231 ∈ COMPOSITE. Możesz łatwo sprawdzić, czy na kartce papieru bez świadka, udowodnienie, że 467231 nie jest liczbą pierwszą, byłoby trudne bez użycia komputera.

Nie powiedzieliśmy nic o tym, jak odpowiedni może być świadek znaleziono. To jest niedeterministyczna część.

Klasa NP zawiera wszystkie języki L , dla których istnieje maszyna Turinga V , który weryfikuje L i stałą k ∈ N taką, że dla każdego input ( w , c ), V zatrzymuje się po co najwyżej T (| w |) kroki dla funkcji T ∈ O ( n ↦ n^k ).

Zauważ, że powyższa definicja oznacza, że dla każdego w ∈ L istnieje świadek c z | c | ≤ T (| w |). (Maszyna Turinga prawdopodobnie nie może 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 .

Faktoryzacja liczb całkowitych nie jest językiem per se. Możemy jednak skonstruować język, który reprezentuje problem decyzyjny z nim związany. Oznacza to, że język, który zawiera wszystkie krotki ( n , m ) takie, że n ma czynnik d z d ≤ m . Nazwijmy ten język FACTOR. Jeśli masz algorytm decydujący o FACTOR, można go użyć do obliczenia pełnej faktoryzacji z tylko narzutem wielomianowym, wykonując rekurencyjne wyszukiwanie binarne dla każdego czynnika pierwszego.

Łatwo jest pokazać, że FACTOR jest w NP . Odpowiednim świadkiem byłby po prostu sam czynnik d , a weryfikator musiałby jedynie 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 i że jest to logarytmiczne w n .)

Jeśli potrafisz wykazać, że FACTOR jest również w P , możesz być pewien, że zdobędziesz 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 to deterministycznie. Po prostu przeprowadza wyczerpujące przeszukiwanie wszystkich świadków. (Zauważ, że maksymalna długość świadka jest ograniczona wielomianem.) Zatem twój algorytm decydujący o PRIMES był w rzeczywistości algorytmem brutalnej siły decydującym o KOMPOZYCJI.

Aby odpowiedzieć na twoje ostatnie pytanie, musimy wprowadzić redukcję . Redukcje to bardzo potężna koncepcja informatyki teoretycznej. Redukcja jednego problemu do drugiego zasadniczo oznacza rozwiązanie jednego problemu poprzez rozwiązanie innego problem.

Niech Σ będzie alfabetem, a A i B to języki powyżej Σ . A to wielomian wiele jeden redukowalny do B , jeśli istnieje funkcja f : Σ ^＊ → Σ ^＊ z następującymi właściwościami.

• w ∈ A   ⇔   f ( w ) ∈ B   dla wszystkich w ∈ Σ ^＊ .
• Funkcja f może zostać obliczona przez maszynę Turinga dla każdego wejścia w w kilku krokach ograniczonych wielomianem w | w |.

W tym przypadku piszemy A ≤ _p B .

Dla Przykładowo, niech A będzie językiem zawierającym wszystkie wykresy (zakodowane jako macierz sąsiedztwa), które zawierają trójkąt. (Trójkąt to cykl o długości 3.) Niech dalej B będzie językiem zawierającym wszystkie macierze ze śladami niezerowymi. (Ślad macierzy jest sumą jej głównych elementów przekątnych). Wtedy A jest wielomianem wielokrotnym w czasie, który można zredukować do B . Aby to udowodnić, musimy znaleźć odpowiednią funkcję transformacji f . W tym przypadku możemy ustawić f , aby obliczyć potęgę 3 ^rd macierzy sąsiedztwa. Wymaga to dwóch iloczynów macierzy-macierzy, z których każdy ma złożoność wielomianową.

Jest rzeczą trywialną, że L ≤ _p L . (Czy możesz to oficjalnie udowodnić?)

Teraz zastosujemy to do NP .

Język L to NP -hard wtedy i tylko wtedy, gdy L „≤ _p L dla każdego języka L ” ∈ NP .

An NP – twardy język może, ale nie musi, znajdować się w samym NP .

Język L to NP -complete wtedy i tylko wtedy, gdy

• L ∈ NP i
• L jest NP -twarda.

Najbardziej znanym kompletnym językiem NP jest SAT. Zawiera wszystkie formuły boolowskie, które można spełnić. Na przykład ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Prawidłowy świadek to { a = 1, b = 0}. Formuła ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Jak byś to udowodnił?)

Nie jest trudno pokazać, że SAT ∈ NP . Pokazanie twardości SAT NP to trochę pracy, ale zostało wykonane w 1971 roku przez Stephen Cook .

Kiedy poznano kompletny język NP , stosunkowo łatwo było wykazać kompletność NP innych języków poprzez redukcję. Jeśli wiadomo, że język A jest NP -twardy, to pokazanie, że A ≤ _p B pokazuje, że B jest również NP -twardy (poprzez przechodniość „≤ _p ”). W 1972 roku Richard Karp opublikował listę 21 języków, które mógł pokazać, że są NP -kompletne poprzez (przechodnią) redukcję SAT. (Jest to jedyny artykuł w tej odpowiedzi, który tak naprawdę polecam przeczytać. W przeciwieństwie do innych, nie jest trudny do zrozumienia i daje bardzo dobre wyobrażenie o tym, jak działa udowodnienie NP -kompletności poprzez redukcję. )

Na koniec krótkie podsumowanie. Użyjemy symboli NPH i NPC , aby oznaczyć klasy języków NP – twardych i NP – kompletnych odpowiednio.

• P ⊆ NP
• NPC ⊂ NP i NPC ⊂ NPH , właściwie NPC = NP ∩ NPH z definicji
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Zwróć uwagę, że włączenie NPC ⊂ NP jest właściwe nawet w przypadku, gdy P = NP . Aby to zobaczyć, wyjaśnij, że żaden nietrywialny język nie może zostać zredukowany do trywialnego, a trywialne języki są również w P jako nietrywialne języki w NP s jest jednak (niezbyt interesującym) przypadkiem narożnym.

Dodatek

Wydaje się, że głównym źródłem nieporozumień jest myśl o „ n ”w„ O ( n ↦ f ( n )) ”Jako interpretacja danych wejściowych algorytmu, gdy w rzeczywistości odnosi się do długości danych wejściowych. Jest to ważna różnica, ponieważ oznacza, że asymptotyczna złożoność algorytmu zależy od kodowania użytego do wprowadzania danych.

W tym tygodniu nowy rekord największej znanej Mersenne prime został osiągnięty. Największa obecnie znana liczba pierwsza to 2 ^{74   207   281} – 1. Ta liczba jest ogromna że boli mnie głowa, więc użyję mniejszego w następującym przykładzie: 2 ³¹ – 1 = 2   147   483   647. Można go zakodować na różne sposoby.

• za pomocą wykładnika Mersennea jako liczby dziesiętnej: 31 (2 bajty)
• jako liczba dziesiętna: 2147483647 (10 bajtów)
• jako jednoargumentowe number: 11111…11 gdzie … ma zostać zastąpione przez 2   147   483   640 więcej 1 s (prawie 2 GiB)

Wszystkie te ciągi kodują tę samą liczbę, a biorąc pod uwagę dowolne z nich, możemy z łatwością skonstruować dowolne inne kodowanie tej samej liczby (możesz zastąpić kodowanie dziesiętne binarnym, ósemkowym lub szesnastkowym mal, jeśli chcesz. Zmienia tylko długość o stały współczynnik.)

Naiwny algorytm do testowania pierwszości jest tylko wielomianem dla jednoargumentowych kodowań. Test pierwszości AKS jest wielomianem dla liczb dziesiętnych (lub dowolnej innej podstawy b ≥ 2 ). Test pierwszości Lucas-Lehmer jest najbardziej znanym algorytmem dla liczb pierwszych Mersennea M _p z p nieparzystą liczbą pierwszą, ale nadal jest wykładnicza w długości kodowania binarnego wykładnika Mersennea p (wielomian w p ).

Jeśli chcemy porozmawiać 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. To znaczy binarne dla liczb całkowitych. (Zwróć uwagę, że nie każda liczba pierwsza jest liczbą pierwszą Mersennea, więc użycie wykładnika Mersennea nie jest ogólnym schematem kodowania.)

W kryptografii teoretycznej do wielu algorytmów formalnie przekazywany jest całkowicie bezużyteczny ciąg k 1 s jako pierwszy parametr. Algorytm nigdy nie sprawdza tego parametru, ale pozwala formalnie na wielomian w k , który jest parametrem bezpieczeństwa używane do dostrajania bezpieczeństwa procedury.

W przypadku niektórych problemów, dla których językiem decyzyjnym w kodowaniu binarnym jest NP -kompletny, język decyzji nie jest już NP -kompletne, jeśli kodowanie osadzonych liczb jest przełączone na jednoargumentowe. Języki decyzyjne dla innych problemów pozostają NP – kompletne nawet wtedy. Te ostatnie nazywane są zdecydowanie NP -kompletne . Najbardziej znanym przykładem jest pakowanie do pojemników .

Interesujące jest również (a może bardziej) zobaczyć, jak złożoność algorytmu zmienia się, jeśli dane wejściowe są skompresowane . Na przykładzie liczb pierwszych Mersenne widzieliśmy trzy kodowania, z których każde jest logarytmicznie bardziej skompresowane niż jego poprzednik.

W 1983 roku Hana Galperin i Avi Wigderson napisał interesujący artykuł o złożoności popularnych algorytmów grafowych, gdy kodowanie danych wejściowych wykresu jest skompresowane logarytmicznie. W przypadku tych danych wejściowych język wykresów zawierających trójkąt z góry (gdzie był wyraźnie w P ) nagle staje się NP -kompletny.

I to ponieważ klasy językowe, takie jak P i NP , są zdefiniowane dla języków , a nie dla problemów .

Komentarze

• Ta odpowiedź prawdopodobnie nie jest przydatna dla poziomu zrozumienia pytającego. Przeczytaj pozostałe odpowiedzi i zobacz, z czym Nanako boryka się. Czy myślisz, że to odpowiedź pomoże mu / jej?
• Ta odpowiedź może nie pomóc OP, ale z pewnością pomoże innym czytelnikom (łącznie ze mną).
• bardzo pomocna odpowiedź! Powinienem rozważyć poprawienie nieprawidłowych symboli matematycznych wyświetlane.

Postaram się podać mniej nieformalną definicję tego samego.

Problemy typu P: problemy, które można rozwiązać w czasie wielomianowym. Zawiera problemy, które można skutecznie rozwiązać.

Problem NP: problemy, które można zweryfikować w polno mial czas. Na przykład: sprzedawca w podróży, projektowanie obwodów. Problemy NP są czymś w rodzaju łamigłówek (jak sudoku). Mając poprawne rozwiązanie problemu, możemy sprawdzić nasze rozwiązanie bardzo szybko, ale jeśli faktycznie spróbujemy go rozwiązać, może to zająć wieczność.

Teraz P vs NP pyta, czy problem, którego rozwiązanie można szybko rozwiązać sprawdzone pod kątem poprawności, czy zawsze istnieje szybki sposób rozwiązania tego problemu. Pisząc zatem w kategoriach matematycznych: czy NP jest podzbiorem P, czy nie?

A teraz wracając do NP kompletny: to są naprawdę trudne problemy problemów NP. Dlatego jeśli istnieje szybszy sposób rozwiązania NP complete, wtedy NP complete staje się P, a problemy NP zamieniają się w P.

NP trudne: problemy, których nawet nie można sprawdzić w czasie wielomianu, są np. Trudne. Na przykład wybranie najlepszego ruchu w szachach jest jednym z nich.

Jeśli coś pozostaje niejasne, spróbuj obejrzeć ten film: https://www.youtube.com/watch?v=YX40hbAHx3s

Mam nadzieję, że to zapewni rozmyty kontur.