Jaki byłby wpływ P = NP? [Zamknięte]

18

Przygotowuję się do testu i nie mogę znaleźć jasnej odpowiedzi na pytanie: Jaki byłby wpływ udowodnienia, że ​​PTIME = NPTIME. Sprawdziłem wikipedię i wspomniałem tylko, że miałoby to „głęboki wpływ na matematykę, sztuczną inteligencję, algorytmy…” itd.

Czy ktoś może dać mi odpowiedź?

latusaki
źródło
W żaden sposób nie ma to związku z tworzeniem oprogramowania. Na razie zamknąłem, ale zapytałem modów w Math.StackExchange, czy chcieliby, żebym to dla ciebie zmigrował.
wałek klonowy

Odpowiedzi:

22

Pierwszą rzeczą, która przychodzi na myśl, jest to, że bezpieczeństwo kryptografii klucza publicznego zależy obecnie od niemożności rozwiązania problemów matematycznych z użyciem siły brutalnej, które należą do klasy trudności NP. Jeśli P = NP, wszystko, co zależy od PKC (w tym HTTPS, co oznacza całą nowoczesną, ogólnoświatową infrastrukturę e-commerce ) musiałoby zostać przerobione!

Mason Wheeler
źródło
4
Zapewniłoby to, że istnieją algorytmy działające w czasie wielomianowym. Byłoby to tylko odliczanie do znalezienia tych algorytmów, a następnie kaboom, że tak powiem.
Inżynier świata
7
Dowód wymagałby znalezienia algorytmu wielomianowego czasu dla problemu pełnego NP. A kiedy znajdziesz jeden algorytm wielomianowy, możesz go użyć do rozwiązania wszystkich innych problemów związanych z NP-zupełnością poprzez zredukowanie problemów do wspólnej formy. Oznacza to, że dowód na P = NP i algorytmy, które go używają, pojawią się w tym samym czasie.
Oleksi
7
Oczywiście stałe czynniki mogą być tak duże, że może to być tylko teoretyczny problem ... przez pewien czas.
quant_dev
17
Kiedy znajdziemy taki algorytm, może on nadal mieć strasznie wysoki stały współczynnik lub mieć ogromny stopień (n ^ 10000 jest wielomianem, ale dla wielu praktycznych celów jest znacznie gorszy niż niewielka wykładnicza złożoność). Oczywiście byłby to znak ostrzegawczy dla wszystkich, aby odeszli od starych metod, tak jak odeszliśmy od DES, zanim udowodniono, że jest to możliwe do rozwiązania, ale światowa gospodarka nie upadłaby natychmiast. Pomyśl tylko o samych pieniądzach: wszyscy ostatecznie wiedzą, że tak naprawdę nie działają, chyba że w to uwierzysz, ale globalny handel nadal działa dobrze.
Kilian Foth
5
Prawdopodobnie skorzystalibyśmy z jednorazowych padów. Amazon może wysłać Ci 1-gigdrive-pendrive, który działałby z jego witryną i utrzymywał cię przez resztę życia.
Macneil
18

Jest to omówione w statusie problemu P kontra NP . Zdecydowanie warte przeczytania.

Kilka istotnych punktów z artykułu (cytowanych z sekcji What If P = NP? ):

  • Kryptografia z kluczem publicznym staje się niemożliwa.
  • Ponieważ wszystkie problemy związane z optymalizacją NP-complete stają się łatwe, wszystko będzie znacznie wydajniejsze. Transport wszystkich formularzy zostanie zaplanowany optymalnie, aby przemieszczać ludzi i towary szybciej i taniej. Producenci mogą poprawić swoją produkcję, aby zwiększyć prędkość i zmniejszyć ilość odpadów.
  • Nauka staje się łatwa dzięki zastosowaniu brzytwy Ockhama - po prostu znajdujemy najmniejszy program zgodny z danymi. Niemal doskonałe rozpoznawanie wzroku, rozumienie i tłumaczenie języka oraz wszystkie inne zadania edukacyjne stają się trywialne. Będziemy także mieli znacznie lepsze prognozy pogody, trzęsień ziemi i innych zjawisk naturalnych.
  • P = NP miałoby również duże implikacje w matematyce. Można znaleźć krótkie, w pełni logiczne dowody twierdzeń, ale dowody te są zwykle bardzo długie. Ale możemy zastosować zasadę brzytwy Occam, aby rozpoznać i zweryfikować matematyczne dowody, jak to zwykle napisano w czasopismach. Możemy wtedy znaleźć dowody twierdzeń, które mają dowody o rozsądnej długości na mniej niż 100 stronach. Osoba, która udowodni, że P = NP wróciłaby do domu z Instytutu Gliny nie z czekiem w wysokości 1 miliona dolarów, ale z siódemką (właściwie sześć, odkąd hipoteza Poincarégo wydaje się rozwiązana).
vinaykola
źródło
2
Nie widzę, jak P = NP sugeruje, że kryptografia klucza publicznego jest niemożliwa. Sugeruje (ale nie oznacza), że obecne implementacje nie są tak trudne do złamania, jak wcześniej sądziliśmy. Ale jak zauważyli inni, jeśli odpowiednie stałe w algorytmie optymalnego skracania czasu są bardzo duże, wówczas P = NP nie miałoby żadnego wpływu na kryptografię klucza publicznego.
emory
+1 za trzeci punkt - wszyscy wiedzą, że P = NP wpłynie na krypto, ale z jakiegoś powodu rzadko słyszysz o tym, jak wpłynie dosłownie na każdą inną dyscyplinę komputerową na planecie.
BlueRaja - Danny Pflughoeft
@emory: Nie będę udawać eksperta, ale rozumiem, że jeśli taki algorytm zostałby znaleziony, nawet przy dość wysokiej stałej, musielibyśmy całkowicie przemyśleć nasze podejście. A kto powie, kiedy algorytm zostanie znaleziony, nie możemy znaleźć innego z mniejszą stałą? Jeden algorytm odblokowałby również wszystkie inne problemy z kompletnym NP. Zatem natychmiastowy efekt może nie być duży, ale trzeba będzie wiele przemyśleć przy zmianie wszystkich istniejących systemów.
vinaykola
pierwszy raz usłyszałem o zasadzie brzytwy Ockhama. Ciekawe rzeczy ...
UmNyobe
@vinaykola udowadniający, że P = NP nie oznacza znalezienia algorytmu. Oczywiście znalezienie algorytmu byłoby najprostszym (ale nie jedynym) sposobem udowodnienia P = NP, a jeśli stałe byłyby rozsądne, moglibyśmy zająć się poruszonymi przez ciebie problemami.
emory
7

Większość kompletnych problemów NP ma „interesujące” zastosowania w prawdziwym życiu. P=NPbędzie miał wiele konsekwencji:

  • Możliwe będzie rozwiązanie dokładnie problemów optymalizacyjnych, które są obecnie przybliżone. Tak jest w przypadku problemu Traveling Salesman i planowania pracy
  • Łamie niektóre środki bezpieczeństwa, które są oparte na tym, że wymagany czas obliczeniowy jest ogromny. Na przykład wiele schematów szyfrowania i algorytmów w kryptografii opiera się na faktoryzacji liczb, najlepiej znanym algorytmie o złożoności wykładniczej. Algorytmy te staną się bezużyteczne, jeśli zostanie znaleziony algorytm wielomianowy.

Podsumowując, chodzi o naturę problemów, o których wiadomo, że są NP-zupełne. Nie są to tylko problemy stworzone przez niewielu naukowców w odległej lokalizacji, aby się wzajemnie bawić. Można je wyrazić w kategoriach biznesowych. W rzeczywistości niektórzy ankieterzy pracy lubią ukrywać problemy z NP w swoich pytaniach w celu przetestowania kandydatów.

UmNyobe
źródło
3
Chociaż faktoryzacja liczb całkowitych jest trudnym problemem, warto zauważyć, że nie jest znana jako NP-zupełna.
dan_waterworth
4
@dan_waterworth: Nie wiadomo, czy rozkład liczb całkowitych jest NP-trudny, ale wiadomo, że jest w NP. [Często wydaje się, że ludzie mówią „NP-zupełny”, gdy mają na myśli „w NP” lub „NP-trudny”. W pewnym sensie byłoby to tak, jakby ktoś powiedział „mniej niż lub równy” w sytuacji, gdy „mniej niż” byłoby bardziej precyzyjne.]
Macneil
5

Możliwości te są omówione w Pięciu światach Impagliazzo .

Oto kilka punktów na wynos:

  • Sztuczna inteligencja byłaby w stanie dokonać ogromnego skoku. Na przykład przy wystarczającej liczbie „danych treningowych” najkrótsze obwody do uzyskania prawidłowych wyników z danych wejściowych stanowią najlepszą metodę tłumaczenia. W szczególności posiadanie doskonałego rozpoznawania mowy i tłumaczenia języka byłoby trywialne. Idąc dalej tym pomysłem, jeśli twoje dane treningowe to filmy nagrodzone Oscarem, mogą wygenerować dla Ciebie więcej filmów nagrodzonych Oscarem.

  • Algorytmy nauczane w szkołach byłyby radykalnie różne. Zamiast uczyć się tak wielu różnych technik algorytmicznych , kursy koncentrowałyby się na ograniczeniu problemów do weryfikacji poprawnych odpowiedzi. To znacznie uprościłoby programowanie.

  • Gospodarka stałaby się znacznie bardziej wydajna. Nastąpiłyby zakłócenia, w tym może przesunięcie programistów. Sama praktyka programowania polegałaby raczej na gromadzeniu danych szkoleniowych, a mniej na pisaniu kodu. Google miałby zasoby, aby przodować w takim świecie.

  • Ponieważ kryptografia klucza publicznego byłaby „niedostępna”, Amazon musiałby wysłać jednorazowy pad na pendrivie w celu dokonania bezpiecznych transakcji.

  • Dowody matematyczne mogą być automatycznie generowane i weryfikowane.

Ogólnie rzecz biorąc, wprowadziłby technologiczną osobliwość; implikacje P = NP byłyby daleko idące. Ponadto Lance Fortnow zajmuje się tym punktem w osobnym poście na blogu , który powinieneś przeczytać.

Macneil
źródło
-1

Wpływ udowodnienia P = NP obejmowałby ponowne zainteresowanie znalezieniem algorytmu redukcji. Ludzie będą również próbować znaleźć pewne dolne granice stałych związanych z algorytmem redukcji.

Udowodnienie, że P = NP nie byłoby tak znaczące, jak twierdzą inne odpowiedzi, ponieważ mogłoby przyjść w postaci zerowego dowodu wiedzy. Znajomość P = NP bez znajomości algorytmu redukcji niewiele różni się od obecnej sytuacji.

Wyobraź sobie, że ktoś udowodnił, że algorytm redukcji istnieje, ale ma wartość O (sqrt (n) + 2 ^ 4096).

emory
źródło
1
W rzeczywistości istnieje wyraźny algorytm redukcji, który jest w P wtedy i tylko wtedy, gdy P = NP. Polega na iteracji wszystkich możliwych programów i równoległym ich uruchamianiu, dopóki nie znajdzie się rozwiązania.
Arthur B
@ArthurB fascynujące. Zakładając, że P = NP, jaka jest kolejność algorytmu?
emory
Nie jest znane, ale jest to optymalna kolejność. scholarpedia.org/article/Universal_search
Arthur B
1
@ArthurB, więc jeśli P = NP, a algorytmem redukcji jest O (n ^ 99999999), to czy P = NP wciąż jest tak wielkim problemem?
emory