Ten artykuł pierwotnie ukazał się na płycie głównej Niemcy. Od czasu swojej pierwotnej publikacji został zaktualizowany o nowe informacje przez Motherboard US. Co mają wspólnego uleczalny rak, sprawiedliwy kapitalizm i idealna gra Super Mario Bros? Zgodnie z teorią matematyczną rozwiązanie każdego z tych problemów pozwoli nam szybko rozwiązać pozostałe., Wszystko, czego potrzeba, to lepsze algorytmy, aby udowodnić, że skomplikowane pytania—takie jak fałdowanie białek, wydajne rynki i analizy kombinatoryczne—są jedynie odmianami prostszych problemów, które superkomputery są już w stanie rozwiązać. Ale jak jeden algorytm może uprościć niezwykle skomplikowane problemy? To zależy od innego pytania: co jeśli skomplikowane problemy są tak naprawdę prostymi problemami w ukryciu?, Zagadka ta pozostaje jednym z największych nierozwiązanych pytań współczesnej matematyki i jest jednym z siedmiu problemów nagrody Milenijnej, za które każda przyjęta odpowiedź jest nagradzana milionem dolarów.
teraz, Niemiecki człowiek o imieniu Norbert Blum twierdzi, że rozwiązał powyższą zagadkę, która jest właściwie znana jako problem P vs NP. Niestety, jego rzekome rozwiązanie nie przynosi dobrych wieści., Blum, który jest z Uniwersytetu w Bonn, twierdzi w swoim niedawno opublikowanym 38-stronicowym artykule, że P nie równa się NP. Innymi słowy, skomplikowane problemy różnią się zasadniczo od prostych problemów i nie wygląda na to, aby nasze wysokowydajne komputery były w stanie złamać te najtrudniejsze problemy w najbliższej przyszłości. Od czasu publikacji jego pracy wielu matematyków zaczęło zadawać pytania, czy Blum w ogóle go rozwiązał.
na czym dokładnie polega Problem P kontra NP?,
Większość informatyków zgadza się z wnioskiem Bluma. Trudne problemy są trudne, łatwe problemy są łatwe. W informatyce proste problemy zwykle mieszczą się pod szyldem P. oznacza to, że można je rozwiązać w „czasie wielomianowym”, co jest bardzo podobne do powiedzenia, że można je rozwiązać w rozsądnym okresie czasu. Znacznie trudniejsze są problemy NP, których komputery nie są w stanie rozwiązać w rozsądnych ramach czasowych. Dla celów praktycznych problemy NP równie dobrze mogą być nierozwiązywalne przez komputery., (Zauważ jednak, że NP oznacza „czas nieeterministyczny wielomianowy”, a nie” czas nie wielomianowy”.) Oto kilka przykładów problemów z NP:
fałdowanie białek: proces, w którym białka w organizmie biologicznym uzyskują swoją strukturę. Lepszy wgląd w ten proces może pomóc nam rozpoznać lub nawet utrudnić mutacje, które mogą wyleczyć pewne formy raka. Zoptymalizowana trasa: zoptymalizowana trasa podróży przez 15 różnych miast bez dwukrotnego odwiedzenia tego samego miasta?, Twardy orzech do zgryzienia, nawet jak na superkomputer, dlatego jest to również uważane za problem NP w informatyce.
idealna gra w szachy: gra w szachy ma nieskończoną liczbę możliwych ruchów, tak że nawet superkomputer o niesamowitej pojemności nie może określić idealnej taktyki. Wielu matematyków uważa ten problem za tak trudny, że nie uważają go za problem NP, ale raczej uważają go za całkowicie poza sferą możliwości.,
wszystkie te złożone problemy mają jedną wspólną cechę: choć znalezienie rozwiązania problemów NP może być trudne, stosunkowo łatwo jest sprawdzić poprawność rozwiązań, gdy już je posiadasz.
te dwa kategoryczne rozróżnienia w złożoności problemów mają początki przed rozwojem społecznym komputerów domowych. W latach 70., kiedy komputery wciąż były wielkości niezgrabnej lodówki, szybko ustalono, że nie wszystkie problemy ludzkości mogą być po prostu rozwiązane przez te maszyny., Zaproponowano, że rozróżnienie może być sformalizowane pod względem złożoności obliczeniowej, co prowadzi do zestawu klas złożoności, w tym N i NP.
od czasu formalnego zdefiniowania P i NP w 1971 roku informatycy zastanawiali się, czy można by wymyślić algorytm zdolny do redukcji lub redefiniowania problemów NP tak, aby można je było rozwiązać w czasie wielomianowym. Gdyby ktoś był w stanie udowodnić, że wszystkie problemy NP są ostatecznie tylko odmianami problemów P, wtedy wszystkie problemy NP zasadniczo podlegałyby tej samej formie redukcji., Innymi słowy, ktokolwiek zna idealną taktykę Super Mario Bros, może również wyleczyć raka.
w sumie 116 najodważniejszych w swojej dziedzinie oficjalnie próbowało rozwiązać tę zagadkę (choć niezliczone więcej informatyków opublikowało niedoszłe rozwiązania do tablic informacyjnych i na stronach takich jak arXiv). Do tej pory żaden z tych dowodów nie został oficjalnie uznany przez społeczność matematyczną.
kto chce zostać milionerem?, dla matematyków
w 2000 roku Clay Mathematics Institute (CMI) z siedzibą w Oksfordzie sporządził listę siedmiu nierozwiązanych problemów nagrody Milenijnej, przeznaczając milion dolarów na każde rozwiązanie. Kto chce zostać milionerem? lub X nagroda dla matematyków. Problemy nagrody Milenijnej są uważane za wyjątkowo trudne nawet w kręgach ekspertów. Bogactwo wiedzy specjalistycznej jest konieczne, aby nawet zrozumieć pytania., Jedynym rozwiązanym do tej pory problemem Millennium Prize jest hipoteza Poincarégo, która nie jest łatwo wyjaśniona w artykule o innym pojęciu matematycznym.
rozwiązanie problemu NP nie byłoby całkiem dobre. Na przykład, większość szyfrowania opiera się na trudności faktoringu bardzo dużych liczb pierwszych. Faktoryzacja całkowita jest problemem klasy NP. 256-bitowy kod, taki jak ten, którego instytucje finansowe używają do płatności kartą kredytową online, jest uważany za niezniszczalny, a tym samym bardzo bezpieczny., Gdyby ktoś udowodnił, że NP jest równe P, banki musiałyby szybko wymyślić inną metodę zabezpieczeń.
Co matematycy sądzą o matematycznym dowodzie Bluma?
odkąd ukazała się praca Bluma, matematycy i informatycy na całym świecie zastanawiają się, czy badacz z Bonn faktycznie rozwiązał ten problem nagrody Milenijnej. Po początkowo pozytywnej reakcji, takiej jak ta ze Stanford matematyk Reza Zadeh, pojawiają się wątpliwości, czy rozumowanie Bluma jest poprawne.,
na forum matematyki teoretycznej, użytkownik o imieniu Mikhail skontaktował się z Aleksandrem Razborowem-autorem artykułu, na którym opiera się dowód Bluma—aby zapytać go o artykuł Bluma. Razborow twierdzi, że odkrył błąd w pracy Bluma: główny argument Bluma jest sprzeczny z jednym z kluczowych założeń Razborowa. I matematyk Scott Aaronson, który jest czymś w rodzaju autorytetu w społeczności matematycznej, jeśli chodzi o p vs., NP, powiedział, że będzie gotów postawić $ 200,000, że matematyczny dowód Bluma nie przetrwa. Aaronson pisze: Jeśli dowód nie został obalony, ” możesz wrócić i powiedzieć mi, że byłem głupcem o zamkniętym umyśle.”W ciągu tygodnia od początkowego wpisu na blogu Aaronsona inni matematycy zaczęli próbować wbić dziury w dowód Bluma. Dick Lipton, profesor informatyki w Georgia Tech, napisał w blogu, że dowód Bluma „przechodzi wiele filtrów powagi”, ale zasugerował, że mogą z nim wystąpić pewne problemy., Komentator tego postu na blogu, znany tylko jako „vloodin”, zauważył ,że w dowodzie był „pojedynczy błąd w subtelnym punkcie”; inni matematycy od tego czasu włączyli się i potwierdzili wstępną analizę vloodina, a więc wyłaniający się konsensus wśród wielu matematyków jest taki, że rozwiązanie dla P vs.NP pozostaje nieuchwytne. Tłumaczenie: Melina McCormack