Jakie byłyby rzeczywiste implikacje konstruktywnego dowodu ?

Rozumiem na wysokim poziomie problem i rozumiem, że gdyby absolutnie „udowodniono”, że jest to prawdą w dostarczonym rozwiązaniu, otworzyłoby to drzwi do rozwiązania wielu problemów w dziedzinie informatyki.$P=NP$

Moje pytanie brzmi: jeśli ktoś opublikowałby niepodważalny, konstruktywny dowód , jakie byłyby natychmiastowe skutki takiego odkrycia? $P=NP$

Nie proszę o opinie na temat tego, jak wyglądałby świat za 5-10 lat. Zamiast tego rozumiem, że jest to tak fundamentalnie nierozwiązywalny problem, że może radykalnie zmienić sposób, w jaki obliczamy ... wiele rzeczy (tak, tutaj pokazuje moja ignorancja ...), których nie możemy dzisiaj łatwo obliczyć .

Jaki niemal natychmiastowy efekt miałby dokładny, dokładny i konstruktywny dowód na praktyczny świat?$P=NP$

Ludzie dali dobre odpowiedzi, zakładając, że z pewną naprawdę dużą stałą. Będę grał optymistą i zakładam, że znajdziemy dowód z możliwą do utrzymania małą stałą. Być może nie jest to prawdopodobne, ale postaram się dać wgląd w to, co by się stało, gdybyśmy mogli skutecznie rozwiązać wszystkie problemy związane z .P = N P N $P=NP$$P=NP$$NP$

• Kompilatory: Niektóre programy komputerowe byłyby nieco szybsze, ponieważ kompilatory używają kolorowania graficznego do przydzielania rejestrów. Bylibyśmy w stanie przydzielić dokładnie dużą liczbę rejestrów. Istniejące kompilatory korzystające z przybliżonego rozwiązania (takiego jak wykresy akordowe) uzyskałyby lepszą wydajność, a te korzystające z dokładnego rozwiązania - szybciej.

• Lokalizacja obiektu: firmy będą w stanie znaleźć optymalne miejsce do umieszczenia fabryk i magazynów dostaw do wysyłki do swoich sklepów, gdy być może są tysiące sklepów i fabryk. Prawdopodobnie nie byłby to ogromny postęp w porównaniu z nowoczesnymi przybliżeniami, ale zmniejszyłby koszty.

• Kupowanie biletów lotniczych: bilety lotnicze są dziwne, ponieważ nie są zgodne z trójkątem równości. Czasami taniej jest latać z A -> B -> C niż bezpośrednio z A -> C, co nie pojawia się podczas modelowania odległości. Łatwo byłoby stworzyć stronę internetową, która znajdzie absolutnie najtańszą sekwencję lotów, które odwiedzają pewną liczbę miast i zaczynają się i kończą w twoim rodzinnym mieście.

• Konstrukcja obwodu: obwody elektryczne na chipie są w zasadzie formułami logicznymi. Rzeczy takie jak minimalizacja mogą być skutecznie obliczone, więc nasz sprzęt stałby się nieco bardziej wydajny.

• Planowanie: wściekły, że Twoja szkoła zdała dwa egzaminy w tym samym czasie? Jeśli twoja szkoła może albo ile potrzebnych przedziałów czasowych, aby żaden uczeń nie miał konfliktu, lub podać określoną liczbę przedziałów czasowych, zminimalizuj liczbę konfliktów.$P=NP$

To tylko próbka praktycznych zastosowań, które przekonalibyśmy się, gdyby kompletność nie była barierą. Jestem pewien, że przegapiłem wiele, ale jeśli dana konstrukcja miałaby dobrą stałą, konsekwencje byłyby daleko idące.$NP$

Niekoniecznie zobaczymy jakieś efekty. Załóżmy, że ktoś znajdzie algorytm, który rozwiązuje 3SAT na zmiennych w podstawowych operacjach. Nie będziesz w stanie uruchomić tego algorytmu w żadnym przypadku, ponieważ trwa on zbyt długo. Albo załóżmy, że znajdzie algorytm działający w podstawowych operacjach. Będziemy mogli używać go tylko w instancjach 3SAT na jednej zmiennej, ponieważ w przypadku większej liczby zmiennych trwa to zbyt długo.2 100 n n $n$$2^{100} n$$n^{100}$

Z drugiej strony załóżmy, że P NP, i że nawet silniejsza wykładnicza hipoteza czasowa. Ogólnie rzecz biorąc, 3SAT powinien być nieuleczalny. Jednak solwery SAT wydają się dobrze radzić sobie z niektórymi problemami.$\neq$

Co tu się dzieje? Istnieje kilka problemów z pytaniem P vs. NP:

1. Dotyczy to tylko najgorszego przypadku.
2. Jest tylko asymptotyczny.
3. Wszystkie wielomianowe ograniczenia czasowe są takie same.

Problemy te podają w wątpliwość jego znaczenie dla realnego świata. Teraz może się zdarzyć, że zostanie znaleziony jakiś naprawdę szybki algorytm dla 3SAT, tak szybki, że nawet szyfrowanie symetryczne stałoby się możliwe do złamania. Ale uważam to za bardzo mało prawdopodobne. Z drugiej strony, P jest całkowicie spójny z tym, że P różni się od NP, a faktoring jest praktyczny; to złamałoby niektóre schematy szyfrowania klucza publicznego. Jest to prawdopodobna sytuacja, która miałaby reperkusje, ale nie ma związku z pytaniem P vs. NP.

Pytanie P vs. NP może być naturalne z matematycznego punktu widzenia, ale jego praktyczne znaczenie jest, moim zdaniem, wątpliwe. Z drugiej strony, badanie tej kwestii może mieć praktyczne konsekwencje; nie kieruje się tym aspektem.

Bardzo ładnie przeczytana jest tutaj [1], w której Impagliazzo rozważa pięć możliwych „światów”, w których relacje między klasami złożoności są różne. Na przykład, w świecie zwanym Algorytmiką (patrz Rozdział 2.1), mamy (lub jakieś inne „moralne odpowiedniki”, takie jak ).N P ⊆ B P $\sf P = NP$$\sf NP \subseteq BPP$

W Algorytmice praktycznie każdy problem optymalizacji byłby trywialny. Językami programowania mogą być języki, w których jeden gatunek powinien mieć pożądane dane wyjściowe w stosunku do danych wejściowych, zamiast określać sposób wykonywania obliczeń. Komputery mogą również znaleźć dowody na dowolne twierdzenie w przybliżeniu na długość dowodu. (Ten widok jest oczywiście bardzo optymistyczny i zależy od wydajnego algorytmu dla niektórych zupełnym zakończeniem).$\sf NP$

[1] Russell Impagliazzo. Osobisty pogląd na złożoność średnich przypadków. Konferencja złożoności, 1995.

Nawet bez P = NP dzisiejsze komputery są niewiarygodnie potężne.

• 12873891274647018937561708356916501047777612653914909670721635802187 może być faktoryzowany przez pojedynczy komputer w niecałe sekundę.
• W przypadku trudniejszych zadań, takich jak synteza układu elektrycznego układu na podstawie opisu jego funkcji na wyższym poziomie lub korekta fotomasek w celu kompensacji artefaktów z procesu produkcyjnego, klastry wielu setek komputerów pracują cały dzień, aby umożliwić niemożliwe.
• Dzisiejsze komputery są w stanie udowodnić twierdzenia matematyczne, których żaden człowiek nie był w stanie udowodnić, na przykład, że algebry Robinsa są logiczne, lub że pewna stała, która przypuszcza się, że jest nieograniczona ( Erdős Discrepancy Problem ) jest większa niż 2.
• Programy do analizy statycznego kodu źródłowego są w stanie zidentyfikować luki w zabezpieczeniach, takie jak błąd Heartbleed .
• Zautomatyzowane narzędzia wnioskowania, takie jak prover9 lub prover -E-twierdzenie są w stanie udowodnić większość typowych charakterystyk algebraicznych odwrotnych półgrup i silnie regularnych pierścieni bez żadnej wyraźnej pomocy.

Edytuj 22 stycznia 2018 r. Teraz dowiedziałem się, jak powinienem „zinterpretować” tekst cytowany w poniższym przykładzie. To była moja wina, że ​​element odwrotny musiał być wyjątkowy . Oto mój plik wejściowy z 22 grudnia 2014 r. ( Addinvrig.in ) i tutaj jest stały plik wejściowy z dzisiaj ( addinvrigFixed.in ). Kluczową kwestią jest to, (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).że siła samych zautomatyzowanych narzędzi wnioskowania wciąż jest dla mnie fascynująca, nawet jeśli nie mogą mnie ocalić przed błędną interpretacją pism innych ludzi.

Korzystanie z automatycznych narzędzi wnioskowania jest dla mnie zaskakująco przydatne, gdy natrafiam na cytowane twierdzenia, w których nie jestem pewien, jak „interpretować” tekst :

W 1974 r. Karvellas [3] badał adwersyjne odwrotne semaging i udowodnił, co następuje:
(Karvellas (1974), Twierdzenie 3 (ii) i Twierdzenie 7) Weź dowolne adwersyjne odwrotne semaging (S, +, ·).
(i) Dla wszystkich , i (ii) Jeśli dla wszystkich a następnie jest dodatkowo przemienny.( x ⋅ y ) ′ = x ′ ⋅ y = $x, y \in S$$(x \cdot y)' = x' \cdot y = x \cdot y'$$x' \cdot y' = x \cdot y$
$a \in aS \cap Sa$$a \in S$$S$

Zaadaptowałem moje pliki wejściowe prover9 do tego twierdzenia i natychmiast został pokazany przeciwny przykład dla cytowanego twierdzenia. Nieznaczna modyfikacja założeń spowodowała powstanie wielu podobnych prawdziwych twierdzeń, co sprawia, że ​​najbardziej prawdopodobne jest, że Karvellas faktycznie stwierdził i udowodnił prawidłowe twierdzenie, które zostało tu przytoczone niepoprawnie. Googling po odniesienie do tego twierdzenia przywołał tylko kolejny artykuł, w którym Karvellas cytował jeszcze mniej dokładnie .

Jest to niewiarygodnie niepełny zbiór wyników wspomaganych komputerowo dla konkretnych problemów, które są na ogół trudne do rozwiązania, jeśli P! = NP. Być może ta kolekcja wyjaśnia przynajmniej niektórym czytelnikom, że wszyscy mamy tendencję do niedoceniania mocy komputerów w tej dziedzinie. Wiele innych odpowiedzi na to pytanie wydaje się sugerować, że nie byłoby dużych konsekwencji, gdyby komputery były (nieco) lepsze w rozwiązywaniu trudnych problemów. Ale komputery coraz lepiej radzą sobie z rozwiązywaniem trudnych problemów (ponieważ sporo czasu i pieniędzy wydaje się, aby tak się stało), a to ma bardzo realne konsekwencje. Gdyby udowodniono, że P = NP, to być może świadomość tego, co komputery mogą faktycznie zrobić (nawet dzisiaj), zwiększyłaby się, a więcej osób użyłoby komputerów, aby pomóc im w takich zadaniach. (PS: Jestem przekonany, że P! = NP,

Istnieje wiele opinii na temat rzeczywistych implikacji P = NP. Jak widać w innych dobrych odpowiedziach, istnieją głównie 2 szkoły myślenia. Jednym z nich jest fakt, że algorytm czasu P może być bardzo trudny lub niewykonalny w rzeczywistości z powodu „nieoczekiwanych anomalii” związanych z abstrakcją. na przykład:

• program może być zbyt „duży”, aby kodować
• może być zaangażowana bardzo duża stała, tak że we wszystkich przypadkach w zasięgu „obliczeń naziemnych” są one nadal długotrwałe, tj. wydajność nie „włącza się”, z wyjątkiem bardzo dużych przypadków. wiadomo, że niektóre algorytmy faktycznie pasują do tego przypadku, jak niedawno zauważył Knuth (pytanie 15)

Zasadniczo szukam większego nacisku na algorytmy, które działają szybko w odniesieniu do problemów, których rozmiar, n, jest możliwy. Większość dzisiejszej literatury poświęcona jest algorytmom, które są asymptotycznie świetne, ale są one pomocne tylko wtedy, gdy n przekracza wielkość wszechświata.

Słynne studium przypadku wykonała Impagliazzo, cytowane przez J. w innej odpowiedzi. Tymczasem jego esej został nieco ekstrapolowany. Oto świetne nowe odniesienie od eksperta, który odpowiada na to pytanie w pewnego rodzaju scenariuszu science fiction, ch2 / p11. zreasumowanie

Złoty bilet: P, NP i poszukiwanie niemożliwego przez Lance'a Fortnowa

• „jeśli okaże się, że P = NP i mamy wydajne algorytmy dla wszystkich problemów związanych z NP, świat zmieni się w taki sposób, że Internet stanie się przypisem w historii. Nie tylko niemożliwe byłoby opisanie wszystkich tych zmian, ale największe implikacje nowych technologii byłyby niemożliwe do przewidzenia ”.

• Algorytm szybko zaimplementowano na superkomputerze. Boeing natychmiast podpisuje umowę, aby uzyskać lepszy projekt skrzydła dla nowego samolotu, umożliwiając mu lot z Londynu do Sydney bez międzylądowania.

• Algorytm wyszukiwania używany do znalezienia nowego algorytmu, który jest jeszcze szybszy, optymalizując oryginalne rozwiązanie P = NP. Kończy się wynikiem 42 milionów wierszy niezrozumiałego kodu. Nazywany „algorytmem Urbana”

• Algorytm wykorzystywany do znajdowania niestandardowych metod leczenia raka / niemal wyleczenia dla poszczególnych osób. leczy raka, AIDS, cukrzycę, ale przeziębienie pozostaje tajemnicą

• Algorytm super harmonogramu pozwala prognostykom „robić niesamowite postępy w prognozowaniu pogody, pozwalając na dokładne przewidywanie temperatury, wiatru, zachmurzenia i opadów atmosferycznych prawie rok wcześniej. Podobne algorytmy ratują teraz życie przez dokładne przewidywanie burz, tornad i huraganów, dzięki czemu ludzie mogą przygotować się lub ewakuować w razie potrzeby. ”

• Bardzo dokładne rozpoznawanie twarzy

• Komputer może rekonstruować modele 3D sceny w czasie rzeczywistym z różnych ujęć kamery

• Algorytmy komputerowe kontrolują operacje kamery na wydarzeniach sportowych (zamiast kontrolowanych przez człowieka)

• Zautomatyzowane komentarze i powtórki są generowane przez algorytm, w tym dobrze wybrane kąty i statystyki, oraz generowane w dowolnym języku w czasie rzeczywistym

• Fantasy baseball / sport nabiera nowego wymiaru dzięki bardzo dokładnym symulacjom

• Algorytmy ulepszają receptury potraw

• Algorytmu można użyć do „uczenia się wszystkiego, w tym wszystkiego, co tworzy dobrą sztukę, muzyki popularnej i słów, które poruszają duszę. Pamiętaj, że P = NP oznacza, że ​​możemy przetestować to, co możemy przetestować. Więc kiedy masz algorytm proces rozpoznawania wielkości, możesz ponownie użyć algorytmu, aby szybko znaleźć tę wielkość. ”

• Polityk używa algorytmu komputerowego do rozpoznawania wspaniałych przemówień i generowania takiego, który pasuje do wzorców. Mowa jest wirusowa w Internecie.

• Ludzie generują pełne dzieła sztuki ze sztuki niepełnej / niedokończonej, np. Symfonii. używają algorytmu do generowania nowych rekordów Beatlesów / Elvisów. Nowa sztuka, powieści, sztuki i poezja, np. Komedia romantyczna z Humphreyem Bogartem / Julią Roberts.

• Amazon może tworzyć niestandardowe powieści dla osób na żądanie. NBC tworzy serial telewizyjny z przygodami na żywo, stworzony całkowicie przez komputer

• Symulowana rzeczywistość wirtualna w grach wideo, umożliwiająca dowolne działania graczy zamiast ustalonego zestawu możliwych fabuł.

• Organy ścigania wykorzystują algorytm jako „niewiarygodne narzędzie w rozwiązywaniu przestępstw, które najwyraźniej uniemożliwiają śledzenie podejrzanych”. algorytm komputerowy może rekonstruować prawdopodobne twarze (w przypadku szkiców kompozytowych) przy użyciu tylko DNA. Policja dopasowuje podejrzanego o morderstwo, przeprowadzając masowe przeszukiwanie bazy danych zdjęć praw jazdy zgodnych z wygenerowanym szkicem (z DNA).

Niestety niewiele z powyższych zarysów Fortnow jest poparte faktyczną literaturą naukową, z wyjątkiem być może pomysłowej ekstrapolacji światów Impagliazzos. rozprawa tego wymagałaby znacznie więcej, ale podsumowując, wydaje się, że jest to zabawne, ale fantastyczne / pobożne życzenie (a może taki jest jego zawoalowany punkt). W rzeczywistości istnieją zasady naukowe, które są sprzeczne z wieloma przedmiotami. I zauważ, że Fortnow jest fanem sportu, więc rozwija w tym obszarze rozszerzoną metaforę, ale czy może to być bardziej wskazówka, że ludzie myślą w groove ?

Na przykład wiadomo, że „efekt motyla” implikuje, że dokładne przewidywanie pogody po (powiedzmy) kilkudniowym horyzoncie jest niemożliwe ze względu na „wrażliwą zależność od warunków początkowych” (a Fortnow później przyznał na swoim blogu, że wielokrotnie krytykuje dokładnie to punkt). Ponadto istnieje wiele dowodów na to, że komputery nie wykonują wysoce subiektywnie ludzkich zadań, takich jak generowanie lub identyfikowanie wpływowej sztuki (zadanie, któremu nawet doświadczeni ludzie nie odnoszą konsekwentnych sukcesów).

Właściwie cała kwestia jest na pograniczu alternatywę lub fałszywej przesłance . Zauważ, że znaczna większość ankietowanych naukowców myśli / wierzy, pomimo braku niepodważalnego dowodu, P ≠ NP. i naturalne jest porównanie go z innymi znanymi prawami / ograniczeniami / ograniczeniami, takimi jak termodynamika (np. niemożność ruchu wiecznego / energia swobodna ) i statystyki, np. „twierdzenie o braku obiadu” .

Podsumowując, być może nawet eksperci-naukowcy nie są w stanie dokładnie przewidzieć wyniku P = NP. Więc może najlepszą odpowiedzią na razie jest przyznanie, że ludzie nie mają obecnie dobrej odpowiedzi.

P vs. NP, technicznie vs. moralnie

Jak powiedział Yuval, możliwe jest, że P = NP jest technicznie prawdziwe, ale moralnie fałszywe. P = NP jest moralnie prawdziwe (nawet jeśli niekoniecznie technicznie), jeśli istnieje szybki algorytm deterministyczny (powiedzmy , a może nawet z małymi stałymi, niczym ), który rozwiązuje jeden ze słynnych problemów NP-zupełnych, takich jak SAT. IIRC, Russell Impagliazzo powiedział kiedyś, że uważa problem P vs. NP za zasadniczo rozwiązany, jeśli ktoś pokaże, że SAT można rozwiązać w czasie .$O(n^2)$$O(n^{\lg^* n})$$2^{65536}+2^{1024}n^{256}$$O(n^{\lg n})$

Co się stanie, jeśli P = NP jest moralnie prawdziwe?

To przypomina nam, dlaczego NP jest tak interesującą klasą problemów. Ogólnie intuicja polega na tym, że często chcemy znaleźć obiekty o rozsądnym rozmiarze (sformalizowane jako rozmiar wielomianowy), które posiadają właściwość a właściwość jest łatwa do zweryfikowania (sformalizowana jako obliczalna w czasie wielomianowym). Ta klasa problemów obejmuje prawie wszystkie problemy, którymi jesteśmy zainteresowani. Aby wyjść poza to, musisz pomyśleć o interakcjach między graczami, takich jak gry. Liczba naturalnych interesujących problemów, których nie ma w NP (lub PH ), jest bardzo mała w porównaniu do naturalnych interesujących problemów NP . Jeśli P = NP jest moralnie$Q$$Q$to prawda, że ​​wszystkie te problemy można rozwiązać bardzo szybko. Aby dać przykład, możesz nauczyć się najlepszych wag dla bardzo skomplikowanych modeli uczenia maszynowego. Możesz złamać protokoły szyfrowania.

Porównanie z przypadkiem, w którym P NP jest moralnie prawdziwe$\neq$

Przez P NP jest prawdą moralną Mam na myśli, że nie możemy rozwiązać SAT (ani żadnego z innych znanych problemów NP-zupełnych) znacznie szybciej niż brutalną siłą, wówczas problemów tych nie da się rozwiązać w praktyce dla ogólnych danych wejściowych nawet o dość niewielkim rozmiarze powiedz 100.$\neq$

Czy P NP jest prawdą moralną, co oznacza, że ​​nie możemy w praktyce rozwiązać problemów trudnych dla NP?$\neq$

Nawet jeśli P NP jest prawdą moralną , nadal możliwe jest, że w przypadku niektórych z tych problemów nie jesteśmy zainteresowani ogólnymi danymi wejściowymi i najgorszym przypadkiem, ale klasą / rozkładem danych wejściowych, które można skutecznie rozwiązać. Np. Może się zdarzyć, że rozwiązanie SAT w uzasadnionym przypadku wymaga czasu wykładniczego, ale w praktyce możemy już rozwiązać SAT na wielu interesujących klasach, takich jak weryfikacja oprogramowania, weryfikacja sprzętu itp. Znacznie szybciej.$\neq$

Jest to trochę podobne do rozwiązania prostszego problemu, np. TSP nie może być nawet efektywnie przybliżone, jeśli P NP jest moralnie prawdziwe, ale już możemy przybliżać szczególny przypadek TSP na grafach euklidesowych.$\neq$

Jeśli wiesz, że chcesz rozwiązać problem NP-complete nie na ogólnych danych wejściowych, ale na danych wejściowych o określonych właściwościach, nie musisz przejmować się ogólnym problemem. Musisz tylko rozwiązać prostszy problem. Niestety często niełatwo jest ustalić, o jakie dane dbają w praktyce.

Wciąż heurystyka może zadziwiająco dobrze sprawdzać się w praktyce, co widzimy w SAT lub programowaniu całkowitym lub uczeniu maszynowym. ( Nauka PAC przy użyciu bardzo prostego modelu 3-DNF jest trudna, jeśli NP RP , a wielu ekspertów uważa, że ​​RP = P).$\neq$

Jaki niemal natychmiastowy efekt miałby dokładny, dokładny dowód P = NP z dostarczonym rozwiązaniem na praktyczny świat?

Prawdopodobnie powstanie wiele wspaniałych rzeczy, ale nikogo to nie obchodzi.

Problem polega na tym, że podstawą (prawie) wszystkich współczesnych metod szyfrowania jest założenie, że P nie jest równe NP. Szyfrowanie, które chroni twoje hasło podczas przesyłania przez Internet i zapisywania go w bazach danych. Szyfrowanie, które chroni dane kart kredytowych, gdy przechodzi przez Internet ... Szyfrowanie, które chroni miliardy codziennych transakcji finansowych, które wiążą naszą globalną gospodarkę z gigantycznym organizmem.

Najlepszy przypadek, P = NP oznacza, że ​​się zatrzymuje. Ludzie wracają do korzystania z gotówki, a banki próbują rejestrować wypłaty gotówki na jakimś niepowiązanym nośniku, ponieważ transakcje z centralą nie są już wiarygodne. Trwa to może kilka miesięcy, dopóki globalne szyfrowanie nie zostanie wdrożone. Najlepszy przypadek

W najgorszym przypadku P = NP oznacza, że ​​ktoś niszczy świat. Waluta opiera się na koncepcji zaufania. Cenisz dolara, ponieważ ufasz, że twój sąsiad da ci za niego towary lub usługi warte dolara. Cenisz swój komputer, mówiąc, że masz w banku 500 dolarów, ponieważ możesz przesunąć kartę i uzyskać towary i usługi warte 500 dolarów ...

Co zrobić, jeśli nie mógł wierzyć, że? Jeśli P = NP, ktoś mógłby podszyć się pod różne banki, rząd, ludzi - i skutecznie losować ilość waluty na każdym koncie. Usuń walutę z każdego konta. Jasne, różne banki mają na to kopie zapasowe, ale jak długo złamano ich szyfrowanie? Które transakcje były dobre, a które podszywane? Nie można tego wiedzieć.

Po zerwaniu zaufania następuje chaos. Wszelkie korzyści wynikające z możliwości radzenia sobie z problemem podróżującego sprzedawcy (na przykład) są ignorowane, ponieważ ludzie mają trudności z wyżywieniem.

Rzeczywistość jest prawdopodobnie gdzieś pośrodku, ale mam nadzieję, że daje to wystarczająco duży obraz tego, jak ważny jest to problem.

Nastąpi ogromny spadek kosztów sprzętu, elektryczności i chmur. Wiele rzeczy jest obecnie obliczanych za pomocą brutalnej siły lub przybliżeń, które wciąż używają silnego brutalnego wymuszania. Nie będziemy już wykonywać tych wszystkich masowo sparaliżowanych obliczeń brutalnej siły.

Nie jest to bynajmniej jedyne zastosowanie przetwarzania w chmurze, ale nadal będzie to zauważalny czynnik w zużyciu energii, przetwarzaniu w chmurze itp. Tylko oszczędności energii mogą być zauważalne na naszym śladzie węglowym.

AI również stanie się znacznie lepsza. Możemy wreszcie mieć komputer, który może być najlepszym graczem GO, a Twój kalkulator graficzny pokona Cię w szachy.

Nie spodziewałbym się rewolucji. Nauczyliśmy się żyć w świecie, w którym P NP, i znaleźliśmy obejścia, w których były one krytyczne (takie jak przybliżone rozwiązania).$\ne$

Odrzucenie przypuszczenia nie oznacza, że ​​wszystkie problemy praktycznej użyteczności zostałyby rozwiązane jednym ruchem palca. Po pierwsze, wciąż mogą być trudniejsze niż NP.