P kontra NP

P versus NP to następujące pytanie interesujące ludzi pracujących z komputerami i w matematyce: Czy każdy rozwiązany problem, którego odpowiedź może być szybko sprawdzona przez komputer, może być również szybko rozwiązany przez komputer? P i NP to dwa rodzaje problemów matematycznych, o których mowa: P problemy są szybkie do rozwiązania przez komputery, a więc są uważane za "łatwe". Problemy NP są szybkie (a więc "łatwe") do sprawdzenia przez komputer, ale niekoniecznie są łatwe do rozwiązania.

W 1956 roku Kurt Gödel napisał list do Johna von Neumanna. W liście tym Gödel pytał, czy pewien problem NP-zupełny może być rozwiązany w czasie kwadratowym lub liniowym. W 1971 roku Stephen Cook przedstawił precyzyjne sformułowanie problemu P versus NP w swoim artykule "The complexity of theorem proving procedures".

Dziś wielu ludzi uważa ten problem za najważniejszy otwarty problem w informatyce. Jest to jeden z siedmiu problemów nagrodzonych nagrodą milenijną, wybranych przez Clay Mathematics Institute, w którym za pierwsze poprawne rozwiązanie przewidziana jest nagroda w wysokości 1 000 000 USD.

Wyjaśnienia

Na przykład, jeśli masz problem, a ktoś mówi "Odpowiedź na twój problem jest zestaw liczb 1, 2, 3, 4, 5", komputer może być w stanie, szybko, aby dowiedzieć się, czy odpowiedź jest dobra czy zła, ale może to zająć bardzo dużo czasu dla komputera, aby faktycznie wymyślić z "1, 2, 3, 4, 5" na własną rękę. Innym przykładem jest znajdowanie liczb pierwszych. Łatwo jest sprawdzić, czy dana liczba jest pierwsza, ale bardzo trudno jest znaleźć te liczby w pierwszej kolejności. Dla niektórych interesujących, praktycznych pytań tego rodzaju, nie mamy żadnego sposobu na szybkie znalezienie odpowiedzi, ale jeśli otrzymamy odpowiedź, możliwe jest sprawdzenie - to znaczy, zweryfikowanie - tej odpowiedzi szybko. W ten sposób o problemach NP można myśleć jak o zagadkach: wymyślenie odpowiedzi na zagadkę może być trudne, ale gdy się ją usłyszy, odpowiedź wydaje się oczywista. W tym porównaniu (analogii) podstawowe pytanie brzmi: czy zagadki są rzeczywiście tak trudne, jak nam się wydaje, czy też coś nam umyka?

Ponieważ tego rodzaju pytania typu P versus NP są tak praktycznie ważne, wielu matematyków, naukowców i programistów komputerowych chce udowodnić ogólną tezę, że każdy szybko sprawdzalny problem może być również szybko rozwiązany. To pytanie jest na tyle ważne, że Instytut Matematyczny Clay da 1 000 000 dolarów każdemu, kto z powodzeniem dostarczy dowód lub ważne wyjaśnienie, które je obali.

Zagłębiając się nieco głębiej, widzimy, że wszystkie problemy P są problemami NP: łatwo jest sprawdzić, czy rozwiązanie jest poprawne, rozwiązując problem i porównując dwa rozwiązania. Jednak ludzie chcą wiedzieć o czymś przeciwnym: Czy istnieją jakieś problemy NP inne niż problemy P, czy też wszystkie problemy NP są tylko problemami P? Jeśli problemy NP rzeczywiście nie są takie same jak problemy P (P ≠ NP), oznaczałoby to, że nie mogą istnieć żadne ogólne, szybkie sposoby rozwiązywania tych problemów NP, bez względu na to, jak mocno byśmy szukali. Jeśli jednak wszystkie problemy NP są problemami P (P = NP), oznaczałoby to, że nowe, bardzo szybkie metody rozwiązywania problemów istnieją. Po prostu nie udało nam się ich jeszcze znaleźć.

Ponieważ najlepsze wysiłki naukowców i matematyków nie znalazły jeszcze ogólnych, łatwych metod rozwiązywania problemów NP, wielu ludzi wierzy, że istnieją problemy NP inne niż problemy P (to znaczy, że P ≠ NP jest prawdziwe). Większość matematyków również uważa to za prawdę, ale obecnie nikt tego nie udowodnił za pomocą rygorystycznej analizy matematycznej. Gdyby można było udowodnić, że NP i P są takie same (P = NP jest prawdziwe), miałoby to ogromny wpływ na wiele aspektów codziennego życia. Z tego powodu, pytanie o P i NP jest ważnym i szeroko badanym tematem.

Przykład

Przypuśćmy, że ktoś chce zbudować dwie wieże, układając na sobie kamienie o różnej masie. Chce się upewnić, że każda z wież ma dokładnie taką samą masę. Oznacza to, że trzeba będzie ułożyć kamienie w dwóch stosach o tej samej masie. Jeśli ktoś zgadnie, jaki podział skał będzie mu odpowiadał, łatwo będzie sprawdzić, czy miał rację. (Aby sprawdzić odpowiedź, można podzielić skały na dwa stosy, a następnie użyć wagi, aby sprawdzić, czy mają one tę samą masę). Ponieważ łatwo jest sprawdzić ten problem, zwany przez informatyków 'Partition' - łatwiej niż rozwiązać go wprost, jak zobaczymy - nie jest to problem P. []

Jak trudne jest to do rozwiązania, prawda? Jeśli zaczniemy od 100 skał, istnieje 2^{100-1}-1 = 633,825,300,114,114,700,748,351,602,687, czyli około 6.3 x 10^{29} możliwych sposobów (kombinacji) na podzielenie tych skał na dwa stosy. Gdyby codziennie sprawdzać jedną unikalną kombinację skał, zajęłoby to 1,3 x 10^{22} lub 1 300 000 000 000 000 000 000 000 000 lat wysiłku. Dla porównania, fizycy uważają, że wszechświat ma około 1,4 x 10^{10} lat (450 000 000 000 000 000 000 000 lub około 4,5 x 10^{17} sekund, czyli około jednej bilionowej tyle, ile trwałby nasz wysiłek związany z układaniem skał. Oznacza to, że gdyby wziąć cały czas, który upłynął od początku wszechświata, trzeba by w każdej sekundzie sprawdzać ponad dwa tryliony (2 000 000 000 000 000) różnych sposobów podziału skał, aby sprawdzić wszystkie różne sposoby.

Gdyby zaprogramować potężny komputer, aby przetestować wszystkie te sposoby podziału skał, można by sprawdzić 1 000 000 {displaystyle 1 000 000} {\displaystyle 1,000,000}kombinacji na sekundę przy użyciu obecnych systemów. Oznacza to, że do przetestowania wszystkich sposobów podziału skał potrzebne byłyby jeszcze 2 000 000 000 (w stylu 2 000 000) {\displaystyle 2,000,000}bardzo wydajnych komputerów, pracujących od początku istnienia wszechświata.

Może się jednak okazać, że da się znaleźć metodę podziału kamieni na dwa równe stosy bez sprawdzania wszystkich kombinacji. Pytanie "Czy P jest równe NP?" jest skrótem do pytania o to, czy taka metoda może istnieć.

Dlaczego to ma znaczenie

Istnieje wiele ważnych problemów NP, które ludzie nie wiedzą, jak rozwiązać w sposób, który jest szybszy niż testowanie każdej możliwej odpowiedzi. Oto kilka przykładów:

  • Pewien podróżujący sprzedawca chce odwiedzić 100 miast, zaczynając i kończąc podróż w domu. Ma ograniczony zapas benzyny, więc może przejechać w sumie tylko 10 000 kilometrów. Chciałby wiedzieć, czy uda mu się odwiedzić wszystkie miasta bez wyczerpania zapasów benzyny.
  • Szkoła oferuje 100 różnych klas, a nauczyciel musi wybrać jedną godzinę na egzamin końcowy dla każdej klasy. Aby zapobiec oszustwom, wszyscy uczniowie danej klasy muszą zdawać egzamin z tej klasy w tym samym czasie. Jeśli uczeń uczęszcza do więcej niż jednej klasy, to wszystkie te egzaminy muszą odbywać się o innej porze. Nauczyciel chciałby wiedzieć, czy może zaplanować wszystkie egzaminy w tym samym dniu, tak aby każdy uczeń mógł przystąpić do egzaminu z każdej klasy.
  • Rolnik chce zawieźć na targ 100 arbuzów o różnej masie. Musi je zapakować do skrzynek. Każda skrzynka może pomieścić tylko 20 kilogramów bez pęknięcia. Rolnik musi wiedzieć, czy 10 skrzynek wystarczy, by przewieźć wszystkie 100 arbuzów na targ. (To jest banalne, jeśli nie więcej niż jeden arbuz waży więcej niż 2 kg, to do każdej ze skrzyń można włożyć dowolne 10, jeśli nie więcej niż dziesięć arbuzów waży więcej niż 2 kg, to do każdej ze skrzyń można włożyć po jednym z nich, itd. do szybkiego rozwiązania; obserwacja będzie kluczem do każdego szybkiego rozwiązania, takiego jak to czy problem zbioru liczbowego).
  • Duża galeria sztuki ma wiele pokoi, a każda ściana jest pokryta wieloma drogimi obrazami. Właściciel galerii chce kupić kamery do obserwacji tych obrazów, na wypadek gdyby złodziej próbował ukraść któryś z nich. Chciałby wiedzieć, czy wystarczy mu 100 kamer, aby mieć pewność, że każdy obraz będzie widziany przez co najmniej jedną kamerę.
  • Problem kliki: Dyrektor pewnej szkoły ma listę uczniów, którzy są ze sobą zaprzyjaźnieni. Chce znaleźć grupę 10% uczniów, którzy wszyscy są ze sobą zaprzyjaźnieni.

Czas wykładniczy

W powyższym przykładzie widzimy, że mając 100 {styl 100} {\displaystyle 100}skał, istnieje 2 100 {styl 2^{100}} {\displaystyle 2^{100}}sposobów na podzielenie zbioru skał. Przy n {styl n}n skałach istnieją 2 n {styl 2^{n}} {\displaystyle 2^{n}}kombinacji. Funkcja f ( n ) = 2 n {displaystyle f(n)=2^{n}} {\displaystyle f(n)=2^{n}}jest funkcją wykładniczą. Jest to ważne dla NP, ponieważ modeluje najgorszy przypadek liczby obliczeń, które są potrzebne do rozwiązania problemu, a zatem najgorszy przypadek wymaganego czasu.

I jak dotąd, dla trudnych problemów, rozwiązania wymagały rzędu 2 n {styl 2^{n}}{\displaystyle 2^{n}} obliczeń. Dla każdego konkretnego problemu ludzie znaleźli sposoby, aby zmniejszyć liczbę potrzebnych obliczeń. Można wymyślić sposób, aby wykonać tylko 1% liczby obliczeń w najgorszym przypadku i to oszczędza dużo obliczeń, ale to wciąż jest 0,01 × ( 2 n ) {displaystyle 0,01 razy (2^{n}})}{\displaystyle 0.01\times (2^{n})} obliczeń. A każdy dodatkowy kamień wciąż podwaja liczbę obliczeń potrzebnych do rozwiązania problemu. Istnieją spostrzeżenia, które mogą stworzyć metody pozwalające na wykonanie jeszcze mniejszej liczby obliczeń, tworząc wariacje modelu: np. 2 n / n 3 {displaystyle 2^{n}/n^{3}}} {\displaystyle 2^{n}/n^{3}}. Ale funkcja wykładnicza nadal dominuje, gdy n {displaystyle n} nrośnie.

Rozważmy problem planowania egzaminów (opisany powyżej). Ale załóżmy, dalej, że istnieje 15000 studentów. Istnieje program komputerowy, który bierze harmonogramy wszystkich 15000 studentów. To działa w godzinę i wychodzi harmonogram egzaminów tak, że wszyscy studenci mogą zrobić swoje egzaminy w jednym tygodniu. Spełnia wiele zasad (nie back-to-back egzaminy, nie więcej niż 2 egzaminy w każdym 28 godzin okres, ...), aby ograniczyć stres egzamin tygodnia. Program działa przez godzinę podczas przerwy śródsemestralnej i każdy zna swój harmonogram egzaminów z dużą ilością czasu na przygotowanie.

W następnym roku jest jednak o 10 uczniów więcej. Jeśli ten sam program działa na tym samym komputerze, to jedna godzina zamieni się w 2 10 {displaystyle 2^{10}}{\displaystyle 2^{10}} godzin, ponieważ każdy dodatkowy uczeń podwaja obliczenia. To jest 6 {displaystyle 6} {\displaystyle 6}tygodni! Gdyby było 20 uczniów więcej, to

2 20 {displaystyle 2^{20}}{\displaystyle 2^{20}} godzin = 1048576 {displaystyle 1048576}{\displaystyle 1048576} godzin ~ 43691 {displaystyle 43691} {\displaystyle 43691}dni ~ 113 {displaystyle 113} {\displaystyle 113}lat

Tak więc dla 15000 {styl 15000}{\displaystyle 15000} uczniów trwa to jedną godzinę. Dla 15020 {displaystyle 15020}{\displaystyle 15020} uczniów, zajmuje to 113 {displaystyle 113} {\displaystyle 113}lat.

Jak widać, funkcje wykładnicze rosną naprawdę szybko. Większość matematyków uważa, że najtrudniejsze problemy NP wymagają wykładniczego czasu do rozwiązania.

Problemy NP-zupełne

Matematycy mogą pokazać, że istnieją pewne problemy NP, które są NP-zupełne. Problem NP-Complete jest co najmniej tak trudny do rozwiązania, jak każdy inny problem NP. Oznacza to, że jeśli ktoś znalazł metodę szybkiego rozwiązania dowolnego problemu NP-Complete, może użyć tej samej metody do szybkiego rozwiązania każdego problemu NP. Wszystkie problemy wymienione powyżej są NP-Complete, więc jeśli sprzedawca znalazł sposób na szybkie zaplanowanie swojej podróży, może powiedzieć o tym nauczycielce, a ona może użyć tej samej metody do zaplanowania egzaminów. Rolnik mógłby użyć tej samej metody, aby określić, ile pudełek potrzebuje, a kobieta mogłaby użyć tej samej metody, aby znaleźć sposób na zbudowanie wieży.

Ponieważ metoda, która szybko rozwiązuje jeden z tych problemów, może rozwiązać je wszystkie, jest wielu ludzi, którzy chcą ją znaleźć. Jednakże, ponieważ istnieje tak wiele różnych problemów NP-Complete i nikt do tej pory nie znalazł sposobu na szybkie rozwiązanie choćby jednego z nich, większość ekspertów uważa, że szybkie rozwiązanie problemów NP-Complete nie jest możliwe.

Podstawowe właściwości

W teorii złożoności obliczeniowej, klasa złożoności NP-zupełna (w skrócie NP-C lub NPC), jest klasą problemów posiadających dwie własności:

  • Należy do zbioru problemów NP (niedeterministycznych problemów czasu wielomianowego): Każde dane rozwiązanie problemu może być szybko (w czasie wielomianowym) zweryfikowane.
  • Jest to również w zbiorze problemów NP-trudnych: Te, które są co najmniej tak trudne, jak najtrudniejsze problemy w NP. Problemy, które są NP-hard nie muszą być elementami NP; w rzeczy samej, mogą nawet nie być rozstrzygalne.

Przegląd formalny

NP-zupełny jest podzbiorem NP, zbioru wszystkich problemów decyzyjnych, których rozwiązania można zweryfikować w czasie wielomianowym; NP może być równoważnie zdefiniowany jako zbiór problemów decyzyjnych rozwiązywanych w czasie wielomianowym na maszynie. Problem p w NP jest także w NPC wtedy i tylko wtedy, gdy każdy inny problem w NP jest przekształcany na p w czasie wielomianowym. NP-complete miało być używane jako przymiotnik: problemy w klasie NP-complete były jak problemy NP+complete.

Problemy NP-zupełne są badane, ponieważ zdolność do szybkiej weryfikacji rozwiązań problemu (NP) wydaje się korelować ze zdolnością do szybkiego rozwiązywania problemu (P). Stwierdzono, że każdy problem w NP jest szybko rozwiązywany - jako tzw. zbiór problemów P = NP:. Pojedynczy problem w NP-complete jest rozwiązywany szybko, szybciej niż każdy problem w NP również szybko rozwiązywany, ponieważ definicja problemu NP-complete stwierdza, że każdy problem w NP musi być szybko redukowalny do każdego problemu w NP-complete (jest redukowalny w czasie wielomianowym). [1]

Przykłady

Wiadomo, że Boolean satisfiability problem jest NP-zupełny. W 1972 roku Richard Karp sformułował 21 problemów, o których wiadomo, że są NP-zupełne. Są one znane jako 21 NP-zupełnych problemów Karpa. Obejmują one takie problemy jak problem programowania całkowitoliczbowego, który stosuje techniki programowania liniowego do liczb całkowitych, problem plecaka, czy problem pokrycia wierzchołków.

Pytania i odpowiedzi

P: Czym jest problem milenijny?



O: Problem milenijny to jeden z najważniejszych i najtrudniejszych problemów matematycznych tego stulecia, który dotyczy tego, czy każdy problem, który jest łatwy do zweryfikowania przez komputery, jest również łatwy do rozwiązania.

P: Jak możemy sklasyfikować problemy matematyczne?



O: Problemy matematyczne można sklasyfikować jako problemy P lub NP na podstawie tego, czy są one rozwiązywalne w skończonym czasie wielomianowym.

P: Jaka jest różnica między problemami P i NP?



O: Problemy P są stosunkowo szybkie i "łatwe" do rozwiązania przez komputery, podczas gdy problemy NP są szybkie i "łatwe" do sprawdzenia przez komputery, ale niekoniecznie łatwe do rozwiązania.

P: Kto wprowadził problem P versus NP?



Stephen Cook przedstawił problem P versus NP w 1971 roku w swoim artykule "The complexity of theorem proving procedures".

P: Dlaczego problem P versus NP jest ważny?



O: Problem P versus NP jest uważany za najważniejszy otwarty problem w informatyce i jest jednym z siedmiu problemów milenijnych, z nagrodą w wysokości 1 000 000 USD za rozwiązanie, które zostanie opublikowane przez Instytut Claya i przypuszczalnie takie, które zmieni całą matematykę.

P: Czy możliwe jest rozwiązanie problemu NP-zupełnego w czasie kwadratowym lub liniowym?



O: W 1956 roku Kurt Gödel napisał list do Johna von Neumanna z pytaniem, czy pewien problem NP-zupełny można rozwiązać w czasie kwadratowym lub liniowym.

P: Dlaczego wielu matematyków ma nadzieję, że problemy milenijne są ze sobą powiązane?



O: Wiele problemów milenijnych dotyczy powiązanych ze sobą zagadnień, a marzeniem wielu matematyków jest wynalezienie teorii unifikujących.

AlegsaOnline.com - 2020 / 2023 - License CC3