Jeśli P = NP, czy moglibyśmy uzyskać dowody hipotezy Goldbacha itp.?

To naiwne pytanie z mojej wiedzy; z góry przeprasza.

Hipoteza Goldbacha i wiele innych nierozwiązanych pytań w matematyce można zapisać jako krótkie formuły w rachunku predykatów. Na przykład artykuł Cooka „Czy komputery mogą rutynowo odkrywać dowody matematyczne?” formułuje tę hipotezę jako

\forall n [(n > 2) \land 2) | n) \supset \exists r \exists s (P. (r) \land P. (s) \land n = r + s)]

$\forall n [( n > 2 \wedge 2 | n) \supset \exists r \exists s (P(r) \wedge P(s) \wedge n = r + s) ]$

Jeśli ograniczymy uwagę do dowodów wielomianowych, twierdzenia z takimi dowodami są w NP. Więc jeśli P = NP, moglibyśmy ustalić, czy np. Hipoteza Goldbacha jest prawdziwa w czasie wielomianowym.

Moje pytanie brzmi: czy moglibyśmy również przedstawić dowód w czasie wielomianowym?

Edit . Zgodnie z komentarzami Petera Shora i Kaveha powinienem był uzasadnić moje twierdzenie, że moglibyśmy ustalić, czy hipoteza Goldbacha jest prawdziwa, jeśli rzeczywiście jest to jedno z twierdzeń z krótkim dowodem. Czego oczywiście nie wiemy!

cc.complexity-theory proof-complexity automated-theorem-proving proof-search Joseph O'Rourke
źródło

Po pierwsze, aby pokazać krótki (<1000 stron?) Dowód hipotezy Goldbacha, musi istnieć krótki dowód. P = NP nie ma na to wpływu.

Peter Shor,

@Suresh, @Kaveh: Wygląda na to, że się mylisz. Tutaj mamy konkretny przykład problemu z wyszukiwaniem NP. Istotnym tu kwantyfikatorem jest istnienie dowodu (w odpowiednim systemie formalnym) twierdzenia.

Kristoffer Arnsfelt Hansen

Inna uwaga jest taka, że możemy zapisać algorytm, że jeśli P = NP znajdzie dowód na daną instrukcję, jeśli istnieje w czasie wielomian w długości instrukcji i długości najkrótszego dowodu. (ten wielomian jest granicą, która obowiązuje dla wszystkich twierdzeń), będzie to jednak algorytm „astronomiczny”.

Kristoffer Arnsfelt Hansen

@Joe: Nie, mogę teraz zapisać algorytm! (Nawet nie wiem, czy P = NP). Chodzi o to, co jest znane jako Uniwersalne wyszukiwanie Levina.

Kristoffer Arnsfelt Hansen

@Kristoffer: Cool! Nie wiedziałem o LS. Widzę, że Marcus Hutter ulepszył coś w LS: „Najszybszy i najkrótszy algorytm dla wszystkich dobrze zdefiniowanych problemów”. International Journal of Foundations of Computer Science, 13 (3): 431–443, 2002.

Joseph O'Rourke

Odpowiedzi:

W rzeczy samej!

Jeśli P = NP, nie tylko możemy zdecydować, czy istnieje dowód długości n dla hipotezy Goldbacha (lub dowolnego innego wyrażenia matematycznego), ale możemy go również skutecznie znaleźć!

Czemu? Ponieważ możemy zapytać: czy istnieje dowód uzależniony od pierwszego bitu ... to czy istnieje dowód uwarunkowany dwoma pierwszymi bitami ... i tak dalej ...

A skąd byś wiedział n? Po prostu wypróbujesz wszystkie możliwości, w porządku rosnącym. Kiedy robimy krok w i-tej możliwości, próbujemy również krok w każdej z możliwości 1 .. (i-1).

Dana Moshkovitz
źródło

Czy to nie jest uniwersalny algorytm wyszukiwania Levina?

Mohammad Al-Turkistany,

@turkistany: tak, jest!

Dana Moshkovitz

Dana odpowiedziała na pytanie. Ale oto kilka uwag dotyczących strony praktycznej.

$P=NP$ $P=NP$ $P=coNP$

$NP$ $l$ $P=NP$ $l$

$P=NP$ $l$ $l$ $P=NP$ $P$ $DTime(n^2)$ ), można wziąć ten algorytm i uruchomić go, aby sprawdzić dowody wykonalnej, ale bardzo dużej długości, która będzie większa niż jakikolwiek dowód, jaki może kiedykolwiek wymyślić człowiek, a jeśli algorytm nie znajdzie odpowiedzi, wówczas zdanie jest praktycznie niemożliwe do udowodnienia. Sztuczka, o której wspomniała Dana, będzie również działać tutaj, aby znaleźć dowód.

Dla praktycznych środków:

$P=NP$ $DTime(10000n^{10000})$
znajdzie dowód tylko wtedy, gdy taki istnieje (tzn. zdanie nie jest niezdecydowanym zdaniem w ZFC), ponadto dowód powinien być możliwie krótki.
$P\neq NP$ $NP=DTime(n^{\log^* n})$

Kaveh
źródło

(n^{10})

$(n^{10})$