Staram się zrozumieć te klasyfikacje i dlaczego one istnieją. Czy moje rozumowanie jest prawidłowe? Jeśli nie to co?

1. P jest złożonością wielomianową lub dla pewnej nieujemnej liczby rzeczywistej , takiej jak itp. Jeśli problem należy do P, istnieje co najmniej jeden algorytm, który może rozwiązać go od zera w czasie wielomianowym. Na przykład zawsze mogę dowiedzieć się, czy liczba całkowita jest liczbą pierwszą, zapętlając i sprawdzając na każdym kroku, czy dzieli .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP jest niedeterministyczną wielomianową złożonością. Naprawdę nie wiem, co to znaczy być niedeterministycznym. Myślę, że oznacza to, że łatwo jest zweryfikować w czasie wielomianowym, ale może być lub nie być czasem wielomianowym do rozwiązania od zera, jeśli nie znamy jeszcze odpowiedzi. Ponieważ może być rozwiązany w czasie wielomianowym, wszystkie problemy P są również problemami NP. Faktoryzacja liczb całkowitych jest cytowana jako przykład NP, ale nie rozumiem, dlaczego osobiście nie jest to P, ponieważ faktoryzacja próbna wymaga O(sqrt(n))czasu.

3. NP-Complete Nie rozumiem wcale, ale jako przykład przytaczam problem Podróżującego Sprzedawcy. Ale moim zdaniem problemem TSP może być po prostu NP, ponieważ potrzeba czegoś takiego, jak sprawdzenie, czy podano ścieżkę z góry.O(2n n2) time to solve, but O(n)

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

Zasadniczo masz rację co do P i NP, ale nie dotyczy NP-twardego i NP-pełnego.

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

• P jest klasą problemów decyzyjnych, które można rozwiązać w czasie wielomianowym za pomocą deterministycznej maszyny Turinga.

• NP jest klasą problemów decyzyjnych, które można rozwiązać w czasie wielomianowym za pomocą niedeterministycznej maszyny Turinga. Równolegle jest to klasa problemów, które można zweryfikować w czasie wielomianowym za pomocą deterministycznej maszyny Turinga.

• NP-hard to klasa problemów decyzyjnych, do których wszystkie problemy w NP można zredukować w czasie wielomianowym za pomocą deterministycznej maszyny Turinga.

• NP-complete to przecięcie NP-twardego i NP. Równolegle NP-zupełny jest klasą problemów decyzyjnych w NP, do której wszystkie problemy w NP można zredukować w czasie wielomianowym za pomocą deterministycznej maszyny Turinga.

A oto schemat Eulera z Wikipedii pokazujący związki między tymi czterema klasami (przy założeniu, że P nie jest równe NP):

Częścią, o której zakładam, że jesteś najbardziej nieświadomy lub niejasny, jest pojęcie „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 wykorzystanie niektórych inny algorytm B, który rozwiązuje problem Y. Redukcja ta nazywana jest „wielomianową redukcją czasu”, jeśli wszystkie części A inne niż B mają wielomianową złożoność czasową. Jako trywialny przykład problem znalezienia najmniejszego elementu w tablicy można w sposób ciągły zredukować do problemu sortowania, ponieważ można posortować tablicę, a następnie zwrócić pierwszy element posortowanej tablicy.

Jedną z rzeczy, których łatwo pominąć w definicji trudnej NP, jest to, że redukcja przechodzi od problemów NP do trudnych NP, ale niekoniecznie odwrotnie . Oznacza to, że problemy trudne dla NP mogą występować w NP lub w znacznie wyższej klasie złożoności (jak widać na schemacie Eulera), lub mogą nawet nie być problemami rozstrzygalnymi. Dlatego ludzie często mówią coś w stylu „NP-trudny oznacza co najmniej tak samo twardy jak NP”, próbując wyjaśnić to nieformalnie.

Problem zatrzymania jest dobrym przykładem trudnego NP, którego wyraźnie nie ma w NP, jak wyjaśnia Wikipedia :

Łatwo jest udowodnić, że problem zatrzymania jest trudny do wykonania, ale nie do końca. Na przykład problem logicznej satysfakcji można sprowadzić do problemu zatrzymania, przekształcając go w opis maszyny Turinga, która próbuje wszystkich przypisań wartości prawdy, a gdy znajdzie takie, które 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 można rozstrzygać w skończonej liczbie operacji, podczas gdy problem zatrzymania jest, ogólnie rzecz biorąc, nierozstrzygalny.

Faktoryzacja liczb całkowitych jest cytowana jako przykład NP, ale nie rozumiem, dlaczego nie jest to P, ponieważ faktoryzacja próbna zajmuje czas O (sqrt (n)).

Do celów klas złożoności njest to długość danych wejściowych. Więc jeśli chcesz uwzględnić liczbę całkowitą k, nto nie, kale log kliczba bitów (lub cokolwiek innego) potrzeba, aby zapisać liczbę. Faktoryzacja liczb całkowitych jest taka, O(sqrt(k))jak mówisz, ale właśnie o to chodzi .O(sqrt(2n))O(2(n/2))

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

Nie. NP-Hard polega jedynie na tym, jak trudno jest rozwiązać problem.

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

NP-Complete Nie rozumiem wcale

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

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

Niedeterminizm 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 komputer może rozwiązać w czasie wielomianowym, niż może się swobodnie powielać. Okazuje się, że jest to dokładnie ten sam zestaw problemów, które można zweryfikować w czasie wielomianowym.

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 , Σ ⁿ 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} ⁷ to zestaw 7-bitowe kody ASCII { 0000000, 0000001..., 1111111}. { 0, 1} ³² 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 ₀ ∈ N i c ∈ N takie, że dla każdego n ∈ N przy n > n ₀ 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 ³¹ - 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 .

Spróbuję podać ci mniej nieformalną definicję tego samego.

Problemy 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 czasie wielomianowym. Na przykład: Podróżujący sprzedawca, projektowanie obwodów. Problemy NP są jak puzzle (jak sudoku). Biorąc pod uwagę prawidłowe rozwiązanie problemu, możemy szybko sprawdzić nasze rozwiązanie, ale jeśli rzeczywiście spróbujemy go rozwiązać, może to potrwać wiecznie.

Teraz P vs NP faktycznie pyta, czy problem, którego rozwiązanie można szybko sprawdzić, czy jest poprawny, zawsze istnieje szybki sposób na jego rozwiązanie. Zatem pisząc matematycznie: czy NP jest podzbiorem P, czy nie?

Teraz wracamy do NP complete: są to naprawdę trudne problemy z NP. Dlatego jeśli istnieje szybszy sposób na rozwiązanie NP complete, NP complete staje się P, a problemy NP zapadają się w P.

NP hard: problemy, których nie można nawet sprawdzić w czasie wielomianowym, są np. Trudne. Na przykład wybór 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 zapewni to rozmazany kontur.