Jak udowodnić P

Zdaję sobie sprawę, że wydaje się to bardzo głupie (lub zbyt oczywiste, by stwierdzić) pytanie. Jednak w pewnym momencie jestem zdezorientowany.

Możemy pokazać, że P NP$=$ wtedy i tylko wtedy, gdy możemy zaprojektować algorytm, który rozwiązuje dowolny przypadek problemu w NP w czasie wielomianowym.

Nie rozumiem jednak, jak, u licha, możemy udowodnić, że P NP . Przepraszam za następującą podobieństwo, ponieważ może być tak nieistotne, ale mówienie komuś, by udowodnił, że P nie jest równe NP, wydaje mi się mówieniem komuś, by udowodnił, że Bóg nie istnieje.$\neq$

Istnieje szereg problemów, których nie można rozwiązać za pomocą niedeterministycznych automatów skończonych (NFA) o wielomianowej liczbie stanów niezależnie od aktualnej technologii (wiem, że jest to niechlujna definicja). Ponadto mamy dość duży zestaw algorytmów, które powodują pewne kluczowe problemy (najkrótsza ścieżka, minimalne drzewo rozpinające, a nawet suma liczb całkowitych ) problemy z czasem wielomianowym.$1 + 2 + \dots + n$

Moje pytanie w skrócie: Jeśli wierzę, że P NP$=$ , powiedziałbyś „pokaż swój algorytm, który rozwiązuje problem NP w czasie wielomianowym!”. Załóżmy, że wierzę P NP . Więc o co dokładnie zapytasz? Co chciałbyś, żebym pokazał?$\neq$

Odpowiedź jest wyraźnie „twoim dowodem”. Jednak jaki dowód pokazuje, że algorytm nie może istnieć? (w tym przypadku algorytm wielomianowy dla problemu NP )

Są trzy główne sposoby, o których wiem, że mogą udowodnić, że P.$\,\neq\,$NP .

1. $\Omega(n\log n)$$n$$O(n^c)$$c$Złożoność obwodu jest kolejna.

2. Wskazując, że P i  NP mają różne właściwości strukturalne. Na przykład P  jest zamknięty w ramach komplementacji. Gdybyś mógł pokazać, że NP$\,\neq\,$co-NP (tzn. że NP  nie jest zamknięte w ramach komplementacji), to musi być to, że P$\,\neq\,$NP . Oczywiście popycha to problem o jeden poziom głębiej - jak byś udowodnił, że NP$\,\neq\,$co-NP ?

   $\exists\mathrm{SO}$

3. Udowodnij, że jakiś problem nie jest kompletny z NP . Jeśli P$\,=\,$$\emptyset$$\Sigma^*$ $\,\neq\,$NP .

Moje pytanie w skrócie: Jeśli wierzę, że P = NP , powiedziałbyś „pokaż swój algorytm, który rozwiązuje problem NP w czasie wielomianowym!”.

Nie zapominaj, że nadal musisz udowodnić, że Twój algorytm rozwiązuje problem i że działa w czasie wielomianowym.

Załóżmy, że wierzę P ≠ NP . Więc o co dokładnie zapytasz? Co chciałbyś, żebym pokazał?

Najpierw spróbuj wyjaśnić „dlaczego” P ≠ NP i dlaczego ten powód można wykorzystać do udowodnienia P ≠ NP w odpowiedniej strukturze logicznej. Następnie naszkicuj dowód i wyjaśnij, w jaki sposób można obronić jego najbardziej wątpliwe części. Następnie podziel ten dowód na prostsze stwierdzenia, które można zweryfikować niezależnie.

• Na przykład ramy logiczne dostarczone przez ZFC są dobre (nawet w pewnym sensie zbyt dobre) w udowadnianiu istnienia modeli (wyraźnie określonych zbiorów aksjomatów, często nawet spełniających dodatkowe właściwości metalogiczne). Więc jeśli znasz przyczynę P ≠ NP związaną z istnieniem modelu o dziwnych właściwościach, najpierw wyjaśnij ten powód, a następnie pokaż, jak można zbudować odpowiedni model w ZFC.
• Jako nie-przykład uważam, że jednym z powodów „dlaczego” P ≠ NP jest to, że matematyka może przybliżać prawie wszystko, co dzieje się w świecie fizycznym, w tym losowość. Jednak znany jest fakt, że systemy formalne mają bardzo ograniczone możliwości udowodnienia, że ​​dany ciąg, liczba, „obiekt” lub „artefakt” są zasadniczo losowe, więc jest mało prawdopodobne, aby ten powód mógł zostać wykorzystany jako dowód w każdym wyraźnie określonym deterministycznym systemie formalnym. Być może, jeśli zaprojektowałeś system probabilistyczny (kwantowy), w którym można zweryfikować pewne dowody w systemie tylko do skończonego prawdopodobieństwa, w zależności od dostępnych zasobów fizycznych ...
• Jako prawdopodobny nie przykład, prawo wykluczonego środka zasadniczo odzwierciedla statyczny obraz wszechświata (matematycznego), a zatem jest bardzo mało prawdopodobne, aby utrzymało się ono w dynamicznym wszechświecie. Teraz NP = coNP (lub jakikolwiek inny upadek wielomianowej hierarchii) byłby w zasadzie przybliżoną wersją prawa wykluczonego środka w odniesieniu do złożoności czasowej, ale złożoność czasowa jest zbyt bliska dynamicznemu wszechświatowi, aby było to możliwe. Istnieją logiczne ramy, takie jak logika liniowa Girarda, które są w stanie uchwycić dynamiczne aspekty wszechświata, więc ... Zwróć jednak uwagę, że Brouwer był w podobnej sytuacji i już stwierdził niezbędną porażkę programu Hilberta jako fakt w swoim przemówieniu inauguracyjnym Intuitionism and Formalism w 1912 r. (wyjaśniając, dlaczego miałoby to być okrągłe rozumowanie), ale nadal nie był w stanie nawet naszkicować dowodu niekompletności Gödela z 1930 r.
• Jako przybliżony przykład, spróbujmy uchwycić niektóre z dostępnych dowodów na P ≠ NP , a mianowicie wykładniczą dolną granicę dla polytopa podróżującego sprzedawcy i brak możliwości procedur opartych na rozdzielczości dla satysfakcji z powodu słabych zasad szufladki. „Dlaczego” w tym przypadku polega na tym, że pewnej klasy problemów kompletnych NP nie można skutecznie rozwiązać za pomocą algorytmów opartych na pewnych naturalnych (dla rozważanej klasie problemów NP-zupełnych), takich jak formuły programowania liniowego dla TSP lub oparte na rozdzielczości metody sprawdzające dla SAT. Różne artykuły podały różne niezależne powody, dla których można to udowodnić, na przykład w ostatnim tekście na temat TSP podano „ścisły związek między przeformułowaniami programistycznymi płyt półproduktu a jednokierunkowymi kwantowymi protokołami komunikacyjnymi” jako uzasadnienie, podczas gdy ostatni artykuł na temat rozdzielczości przytoczył dwa niezależne powody, mianowicie dolne granice „dla klasy wzorów reprezentujących zasadę szufladki i dla losowo generowanych wzorów”.
  Można również zaobserwować, że z czasem próbowano wzmocnić wyniki. Wstępne wyniki dla TSP dotyczyły jedynie symetrycznego sformułowania programowania liniowego, podczas gdy najnowsze wyniki nie mają takiego ograniczenia, a także dotyczą problemów z maksymalnym cięciem i maksymalnym stabilnym zestawem oprócz TSP. Wstępne wyniki rozstrzygania dotyczyły tylko podstawowych procedur rozwiązywania Davisa-Putnama i jednej klasy sztucznych kontrprzykładów, podczas gdy najnowsze wyniki obejmują duże klasy metod opartych na rozdzielczości i dają wiele klas naturalnie występujących kontrprzykładów.
  W przypadku TSP nie mam pojęcia, w jaki sposób wyniki powinny być dalej wzmacniane, chyba że przez zastosowanie większej liczby problemów oprócz TSP, maksymalnego cięcia i maksymalnego stabilnego zestawu. Jeśli chodzi o rozdzielczość, miałbym wiele pomysłów na dalsze wzmocnienie wyników, ale artykuł, do którego podłączyłem, pochodzi z 2002 r., Stephen Cook i Phuong Nguyen opublikowali w 2010 r. Monografię Logiczne podstawy dowodu złożoności, której nawet nie przejrzałem, a ja myślę, że obejmie już wiele moich pomysłów. Warto zauważyć, jak niewielka jest różnica dla większości z nas, o ile wyniki te zostały z czasem wzmocnione, pomimo naszego zainteresowania P ≠ NPpytanie. Nawet gdyby w międzyczasie udowodniono, że algorytmy oparte na systemach logicznych bez odpowiednika reguły cięcia nie mogą skutecznie rozwiązać problemów z zadowalalnością, nadal uważalibyśmy, że zasadniczo nie odnotowano postępu na P ≠ NP , że problem jest zasadniczo wciąż tak szeroko otwarte jak zawsze.