Złożoność dowodu dowodu lub dowodu P = NP

Czy przeprowadzono badania nad złożonością dowodu rozwiązania problemu P = NP? Jeśli nie, biorąc pod uwagę brak postępów w rozwiązywaniu problemu, czy nie byłoby rozsądne przypuszczać, że jakikolwiek dowód rozwiązujący problem P = NP będzie wymagał wielomianowej liczby kroków?

Wiadomo, że jakikolwiek dowód na dolne granice obwodu super-wielomianowego (które są nieco silniejszymi stwierdzeniami niż ) wymaga super-wielomianowych, nawet wykładniczych dowodów wielkości w słabych systemach, takich jak rozdzielczość. Uogólnienie na silniejsze systemy dowodowe jest dobrze znanym otwartym problemem.$P\neq NP$

Zobacz sekcję 5 tej ankiety autorstwa A. Razborova, gdzie pokazano te rzeczy.

Złożoność dowodu ma sens tylko wtedy, gdy istnieje ciąg instrukcji zależny od parametru . Na przykład, twierdzenie P H P n stwierdza (nieformalnie), że nie ma biosekcji [ n + 1 ] → [ n ] . Ta sekwencja zdań jest trudna w przypadku niektórych systemów dowodu zdania.$n$$\mathsf{PHP}_n$$[n+1] \to [n]$

Instrukcja jest pojedynczą instrukcją, więc nie można bezpośrednio zastosować do niej złożoności dowodu. Jednak następująca sekwencja instrukcji ma sens dla poszczególnych funkcji s ( n ) : „nie ma obwodu o rozmiarze s ( n ) poprawnie rozwiązującego SAT dla instancji o długości n ”. Zostało to uwzględnione w literaturze, na przykład przez Razborova (który rozważał ustawienie jednolitej złożoności dowodu, tj. Ograniczonej arytmetyki).$\mathsf{P} \neq \mathsf{NP}$$s(n)$$s(n)$$n$

Mamy 3 przypadki:

• Istnieje dowód, że . Następnie istnieje algorytm rozwiązujący problem „Wyślij dowód, że P = N P ”, który działa w czasie O ( 1 ) . Zaszyfrowuje dowód w samej maszynie Turinga i wysyła go. Działa w tym samym czasie bez względu na wejście.$P = NP$$P=NP$$O(1)$

• Podobnie, jeśli istnieje dowód, że , to możemy napisać algorytm emitujący ten dowód w czasie O ( 1 ) .$P\neq NP$$O(1)$

• Jeśli nie ma dowodu na żadną z tych spraw, minimalna złożoność znalezienia dowodu na jedno z nich to : żadna Maszyna Turinga nigdy nie może się zatrzymać i wydać dowodu na jedno z nich, ponieważ takich dowodów nie ma.$O(\infty)$

To, że nie znaleźliśmy żadnego dowodu, nie oznacza, że ​​nie istnieje, a klasy złożoności są zdefiniowane w kategoriach tego, co istnieje.

Mówiąc dokładniej, nie możemy dokładnie wiedzieć, jak trudno jest znaleźć dowód lub odwrotnie, dopóki nie poznamy wyniku, który pokonuje punkt.$P=NP$

Wiemy jednak, że problem „Weź stwierdzenie w logice predykatów i ustal, czy istnieje na to dowód” jest nierozstrzygalny. Nie ma więc ogólnych procedur generowania dowodów, do których moglibyśmy podłączyć P vs NP, które gwarantowałyby uzyskanie wyniku.

Jeśli P = NP, wystarczy stworzyć wielomianowy algorytm czasowy do rozwiązania jakiegoś problemu NP-zupełnego i udowodnić, że jest on rzeczywiście wielomianowy (co może być trudne, na przykład algorytm Simplex zwykle działa bardzo szybko, ale udowadnia, że działa szybko wydaje się niezwykle trudne).

$n^{100}$