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

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ź?

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!

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).

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.

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ć.

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).