Nieprzerwalność problemów NP-zupełnych jako zasada fizyki?

Zawsze intryguje mnie brak danych liczbowych z matematyki eksperymentalnej za lub przeciw pytaniu P vs NP. Podczas gdy hipoteza Riemanna zawiera pewne dowody potwierdzające weryfikację numeryczną, nie znam podobnych dowodów na pytanie P vs NP.

Ponadto nie jestem świadomy żadnych bezpośrednich konsekwencji dla świata fizycznego istnienia nierozwiązywalnych problemów (lub istnienia funkcji nieobliczalnych). Zwijanie się białek jest problemem kompletnym dla NP, ale wydaje się, że zachodzi bardzo skutecznie w układach biologicznych. Scott Aaronson zaproponował zastosowanie NP Hardness Assumption jako zasady fizyki. Stwierdza to nieformalnie jako „ problemy NP-zupełne są nierozwiązywalne w świecie fizycznym ”.

Zakładając założenie o twardości NP, dlaczego trudno jest zaprojektować eksperyment naukowy, który decyduje, czy nasz wszechświat przestrzega założenia o twardości NP, czy nie?

Ponadto, czy są jakieś znane dowody liczbowe z matematyki eksperymentalnej za lub przeciw ?$P\ne NP$

EDYCJA: Oto ładna prezentacja Scotta Aaronsona zatytułowana Nieprzerwana obliczalność jako prawo fizyki

Nie sądzę, że fakt, że jest stwierdzeniem asymptotycznym, jest automatycznym „łamaczem”. Można tworzyć konkretne przypuszczenia, które są zgodne z naszą wiedzą, ale silniejsze niż P w porównaniu z NP, np. „Potrzeba co najmniej 2 n / 10 kroków, aby znaleźć satysfakcjonujące przypisanie dla losowej formuły n zmiennej 10SAT” (przy czym „losowy” oznacza np. posadzony model Achlioptas Coja-Oghlan , to tylko przykład - nie wiem, jakie są rozsądne konkretne liczby od ręki).$P\neq NP$$2^{n/10}$

Taka hipoteza może doprowadzić do obalenia prognozy, że każdy naturalny system, który będzie próbował to rozwiązać, zawiedzie (np. Utknie w lokalnych minimach), co można zweryfikować za pomocą eksperymentów. Rzeczywiście, nie jestem ekspertem w tej dziedzinie, ale według mojej wiedzy, jak wspomniał Joe Fitzsimons, takie przewidywania zostały potwierdzone za pomocą obliczeń adiabatycznych. (Scott Aaronson przeprowadził również zabawne eksperymenty z bańkami mydlanymi).

Oczywiście można również zobaczyć „dowody empiryczne” na w tym, że ludzie próbują rozwiązać problemy związane z optymalizacją, szyfrować kryptoanalizę itp. I jak dotąd nie odnieśli sukcesu ...$P \neq NP$

Świat rzeczywisty jest obiektem o stałej wielkości, więc nie ma sposobu, aby wykluczyć wielomianową procedurę w świecie rzeczywistym w celu rozwiązania problemów z całkowitą NP, które mają wielką stałą ukrytą w dużej notacji O.

W każdym razie, poza tym punktem, założeniem jest stwierdzenie formy „nie ma procedury w świecie rzeczywistym, która działałaby ...” Jak zaprojektować eksperyment, który obaliłby takie stwierdzenie? Jeśli założeniem było coś w rodzaju „Jeśli wykonujemy X w prawdziwym świecie, Y się zdarza”, można to obalić, wykonując X. Stwierdzenie, że chcemy, potwierdza nieistnienie czegoś, więc nie widzę eksperymentu podejmowanie decyzji. Może to być pokazane jako fizyczna konsekwencja praw fizyki, ale jest to nawet trudniejsze niż P vs NP, ponieważ maszyna Turinga przestrzega praw fizyki. Ponieważ nie udało nam się nawet wykazać, że TM nie są w stanie rozwiązać problemów z całkowitą NP w czasie wielomianowym, wydaje się całkowicie beznadziejne, aby pokazać, że żaden proces fizyczny nie może rozwiązać problemów z całkowitą NP w czasie wielomianowym.

Rzeczywiście, fizyczna wersja P nie równa się NP, a mianowicie, że żaden naturalny układ fizyczny nie jest w stanie rozwiązać pełnego problemu NP, jest bardzo interesujący. Istnieje kilka obaw

1) Progrem wydaje się praktycznie „ortogonalny” zarówno dla fizyki eksperymentalnej, jak i teoretycznej. Więc tak naprawdę nie zapewnia (jak dotąd) użytecznych informacji z fizyki.

Jest kilka fajnych argumentów, jak można wywnioskować z tej fizycznej wersji hipotezy pewne spostrzeżenia z fizyki, ale te argumenty są dość „miękkie” i mają luki. (I takie argumenty mogą być problematyczne, ponieważ opierają się na bardzo trudnych przypuszczeniach matematycznych, takich jak NP nonot równy P, a NP nie są uwzględnione w BQP, którego nie rozumiemy.)

(Podobny komentarz dotyczy „tezy kościelnej”.)

2) Chociaż fizyczna NP nie równa P jest szerszym przypuszczeniem niż matematyczna NP nie równa P, możemy również uznać ją za bardziej ograniczoną, ponieważ algorytmy występujące w naturze (a nawet algorytmy stworzone przez ludzi) wydają się bardzo ograniczona klasa wszystkich teoretycznie możliwych algorytmów. Bardzo interesujące będzie formalne zrozumienie takich ograniczeń, ale w każdym przypadku każdy „dowód” ćwiczeniowy sugerowany w pytaniu będzie miał zastosowanie tylko do tych ograniczonych klas.

3) W modelowaniu naukowym złożoność obliczeniowa stanowi rodzaj materii drugiego rzędu, w której najpierw chcielibyśmy modelować zjawiska naturalne i zobaczyć, co można przewidzieć na podstawie modelu (odkładając na bok teorię złożoności obliczeniowej). Nadawanie zbyt dużej wagi problemom złożoności obliczeniowej na etapie modelowania nie wydaje się owocne. W wielu przypadkach model jest na początku trudny obliczeniowo, ale nadal może być wykonalny w przypadku naturalnie występujących problemów lub przydatny do zrozumienia zjawisk.

4) Zgadzam się z Boazem, że kwestia asymptotyczna nie jest konieczna do „zerwania umowy”. Jest to jednak dość poważna kwestia, jeśli chodzi o znaczenie złożoności obliczeniowej w modelowaniu w prawdziwym życiu.

Jeśli pozwolisz mi trochę uogólnić ... Rozwińmy pytanie i poproś o inne założenia teoretyczne dotyczące złożoności i ich konsekwencje dla eksperymentów naukowych. (Skupię się na fizyce.) Niedawno był dość udany program, który próbował zrozumieć zestaw dopuszczalnych korelacji między dwoma urządzeniami pomiarowymi, które, mimo że są oddzielone przestrzennie, wykonują pomiar na (prawdopodobnie nielokalnie skorelowanym) układzie fizycznym ( 1). W ramach tej i podobnych konfiguracji można użyć założeń dotyczących twardości złożoności komunikacyjnej, aby uzyskać ścisłe granice, które odtwarzają dopuszczalne korelacje dla mechaniki kwantowej.

Aby dać ci smak, pozwól mi opisać wcześniejszy wynik w tym względzie. Popescu-Rohrlich box (pudełko lub PR) jest wyimaginowany urządzenie, które odtwarza korelacje pomiędzy urządzeniami pomiarowymi, które są zgodne z zasadą, że żadna informacja może podróżować szybciej niż światło (zwana zasada bez sygnalizacji ).

S. Popescu i D. Rohrlich, Kwantowa nielokalność jako aksjomat, Znaleziono. Phys. 24, 379–385 (1994).

Możemy to postrzegać jako przykład złożoności komunikacji, która ma pewien wpływ. Pomysł, że dwóch obserwatorów musi komunikować się domyślnie, zakłada pewne ograniczenie, które fizyk nie nazwałby sygnalizacją. Odwracając ten pomysł, jakie rodzaje korelacji są możliwe między dwoma urządzeniami pomiarowymi ograniczonymi przez brak sygnalizacji? Tak badają Popescu i Rohrlich. Wykazali, że ten zestaw dopuszczalnych korelacji jest ściśle większy niż dozwolony przez mechanikę kwantową, które z kolei są zdecydowanie większe niż te dopuszczone przez fizykę klasyczną.

Powstaje zatem pytanie, co sprawia, że ​​zestaw korelacji kwantowych jest „właściwym” zestawem korelacji, a nie tych, na które nie pozwala żadna sygnalizacja?

Aby odpowiedzieć na to pytanie, załóżmy od podstaw, że istnieją funkcje, dla których złożoność komunikacji nie jest trywialna. Tutaj nietrywialne oznacza po prostu, że wspólne obliczenie funkcji boolowskiej f (x, y) zajmuje więcej niż pojedynczy bit (2). O dziwo, nawet to bardzo słabe założenie teoretyczne złożoności jest wystarczające, aby ograniczyć przestrzeń dopuszczalnych korelacji.

G. Brassard, H. Buhrman, N. Linden, AA Méthot, A. Tapp i F. Unger, Ograniczenie nielokalności w każdym świecie, w którym złożoność komunikacji nie jest trywialna, Phys. Wielebny Lett. 96, 250401 (2006).

Zauważ, że słabszy wynik został już udowodniony w doktoracie. praca Wima van Dam. What Brassard i in. udowodnić, że dostęp do skrzynek PR, nawet tych, które są wadliwe i tylko przez pewien czas dają poprawną korelację, pozwala całkowicie zbanalizować złożoność komunikacji. W tym świecie każda funkcja Boolean z dwiema zmiennymi może być wspólnie obliczona przez przesłanie tylko jednego bitu. To wydaje się dość absurdalne, więc spójrzmy na to odwrotnie. Możemy traktować nietrywialność złożoności komunikacyjnej jako aksjomat, a to pozwala nam wyprowadzić , że w naszych eksperymentach nie obserwujemy pewnych korelacji silniejszych niż kwantowe.

Ten program wykorzystujący złożoność komunikacji okazał się zaskakująco skuteczny, być może nawet bardziej niż odpowiadający mu złożoność obliczeniowa. Powyższe dokumenty to tak naprawdę wierzchołek góry lodowej. Dobrym miejscem do rozpoczęcia dalszej lektury jest ta recenzja:

H. Buhrman, R. Cleve, S. Massar i R. de Wolf, Nielokalność i złożoność komunikacji, Rev. Mod. Phys. 82, 665–698 (2010).

lub przegląd literatury na podstawie dwóch innych cytowanych przeze mnie artykułów.

Rodzi to również interesujące pytanie o to, dlaczego ustawienie komunikacji wydaje się bardziej podatne na analizę niż ustawienie obliczeń. Być może może to być przedmiotem innego opublikowanego pytania na temat cstheory.

(1) Weźmy na przykład eksperymenty mierzące coś znanego jako nierówność CHSH (rodzaj nierówności Bella ), w której układ fizyczny składa się z dwóch splątanych fotonów, a pomiarami są pomiary polaryzacji poszczególnych fotonów w dwóch odległych przestrzennie miejscach.

(2) Ten pojedynczy bit jest konieczny, ilekroć f (x, y) faktycznie zależy zarówno od x, jak i y, ponieważ wysłanie bitów zerowych nie naruszyłoby żadnej sygnalizacji.

Ponadto, czy są jakieś znane dowody liczbowe z matematyki eksperymentalnej za lub przeciw P ≠ N P$P \neq NP$

$NP \subseteq P/poly$ podobnego rodzaju, które znaleziono na hipotezie Riemanna Hipoteza lub Goldbach stosując wyraźne obliczeń, aby wykazać, że, na przykład, SAT do długości 10 nie ma obwody o rozmiarze 20 (gdzie pozwala się zmieniać wartości 10 i 20). To wciąż napotyka ten sam problem poruszony w innych odpowiedziach - skończone dowody nie mogą dać nam asymptotycznej odpowiedzi. Zasadniczo ta sama kwestia dotyczy jednak obecnych „dowodów” na hipotezę Riemanna.

Obecnie znalezienie minimalnego obwodu dla SAT do długości 10 jest obecnie bardzo trudne. Jednak niektóre pomysły teorii złożoności geometrycznej pozwalają uzyskać podobne wyniki przy bardziej wydajnym (myślę, że wykładniczym, a nie podwójnym wykładniczym) wyszukiwaniu obliczeniowym. Jednym z przypuszczeń Mulmuleya jest to, że w rzeczywistości poszukiwania można przeprowadzić w czasie wielomianowym, ale daleko nam do udowodnienia czegokolwiek zbliżonego.

Definicje „czasu wielomianowego” i „czasu wykładniczego” opisują ograniczające zachowanie czasu działania, gdy wielkość wejściowa rośnie do nieskończoności. Z drugiej strony, każdy eksperyment fizyczny koniecznie uwzględnia tylko dane wejściowe o ograniczonym rozmiarze. Zatem nie ma absolutnie żadnego sposobu eksperymentalnego ustalenia, czy dany algorytm działa w czasie wielomianowym, czasie wykładniczym, czy w czymś innym.

Lub innymi słowy: co Robin powiedział.

Zacznę od stwierdzenia, że ​​całkowicie zgadzam się z Robin. Jeśli chodzi o zwijanie białka, istnieje niewielki problem. Podobnie jak w przypadku wszystkich takich systemów, fałdowanie białek może utknąć w lokalnych minimach, co wydaje się być zaniedbywane. Bardziej ogólnym problemem jest po prostu znalezienie stanu podstawowego jakiegoś hamiltonianu. W rzeczywistości, nawet jeśli weźmiemy pod uwagę tylko spiny (tj. Kubity), problem ten jest kompletny dla QMA.

Naturalni hamiltonianie są jednak nieco bardziej miękcy niż niektóre sztuczne stosowane do udowodnienia kompletności QMA (które nie odzwierciedlają naturalnych interakcji), ale nawet jeśli ograniczymy się do naturalnych interakcji między dwoma ciałami w prostych układach, wynikiem jest nadal NP -kompletny problem. Rzeczywiście, stanowi to podstawę podejścia do rozwiązania problemów NP przy użyciu adiabatycznego obliczenia kwantowego. Niestety wydaje się, że to podejście nie zadziała w przypadku problemów z NP-zupełnością, ze względu na raczej techniczny problem związany ze strukturą poziomu energii. Prowadzi to jednak do interesującej konsekwencji istniejących w NP problemów, które z natury nie są skutecznie rozwiązywalne (przez które rozumiem procesy fizyczne). Oznacza to, że istnieją systemy, które nie mogą skutecznie chłodzić. To jest do powiedzenia,

Badanie rzeczywistych sytuacji z perspektywy obliczeniowej jest dość trudne ze względu na ciągły dyskretny „skok”. Podczas gdy wszystkie zdarzenia w świecie rzeczywistym (podobno) są uruchamiane w sposób ciągły, modele, których zwykle używamy, są implementowane w czasie dyskretnym. Dlatego bardzo trudne jest określenie, jak mały lub duży krok powinien być, jaki powinien być rozmiar problemu itp.

Napisałem streszczenie na temat artykułu Aaronsona na ten temat, jednak nie jest to po angielsku. Zobacz oryginalny papier .

Osobiście słyszałem o innym przykładzie problemu ze świata rzeczywistego zamodelowanego w obliczeniach. Artykuł dotyczy modeli układów sterowania opartych na stadzie ptaków. Okazuje się, że chociaż w prawdziwym życiu zajmuje to trochę czasu ptakom, jest on trudny do rozwiązania („wieża 2s”), gdy analizuje się go jako problem obliczeniowy. Szczegółowe informacje można znaleźć w artykule Bernarda Chazelle .

[Edycja: Wyjaśniono część dotyczącą artykułu Chazelle. Dziękujemy za podanie dokładnych informacji.]

Nadal głosuję za problemem n-ciała jako przykładem nietrwałości NP. Panowie, którzy odnoszą się do rozwiązań numerycznych, zapominają, że rozwiązanie numeryczne jest modelem rekurencyjnym, a nie rozwiązaniem w zasadzie takim samym, jak rozwiązanie analityczne. Rozwiązanie analityczne Qui Dong Wanga jest trudne. Białka, które mogą się fałdować, i planety, które krążą w układach więcej niż dwóch ciał, są układami fizycznymi, a nie rozwiązaniami algorytmicznymi, których dotyczy problem P-NP.

Muszę też docenić trudności firmy Chazisop związane z ciągłymi rozwiązaniami. Jeśli czas lub przestrzeń są ciągłe, potencjalne przestrzenie stanu stają się niepoliczalne (aleph jeden).

$n$