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ź?
algorithms
complexity
latusaki
źródło
źródło
Odpowiedzi:
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!
źródło
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? ):
źródło
Większość kompletnych problemów NP ma „interesujące” zastosowania w prawdziwym życiu.
P=NP
będzie miał wiele konsekwencji: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.
źródło
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ć.
źródło
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).
źródło