O wiarygodności P w porównaniu z NP

Po pierwsze, moje rozumienie twierdzenia o niekompletności Gödla (i logiki formalnej w ogóle) jest bardzo naiwne, podobnie jak moja wiedza z zakresu teoretycznej informatyki (co oznacza, że tylko jeden kurs magisterski odbył się, gdy jestem jeszcze studentem), więc pytanie może być bardzo naiwny.

O ile mogłem znaleźć, wiarygodność P w porównaniu z NP jest otwartym problemem.

Teraz:

Pierwsze twierdzenie Gödela o niekompletności stwierdza, że mogą istnieć stwierdzenia, które są prawdziwe, ale nie można ich udowodnić ani obalić.
Jeśli zostanie znalezione rozwiązanie wielomianowe dla problemu NP-zupełnego, dowodzi to, że P = NP.

Załóżmy więc, że P = NP nie da się udowodnić:
oznacza to, że nie można znaleźć przykładu rozwiązania wielomianu dla problemu NP-zupełnego (w przeciwnym razie byłby to dowód).
Ale jeśli nie można znaleźć przykładu rozwiązania wielomianu dla problemu NP-zupełnego, oznacza to, że P = NP jest fałszywe (udowadnianie, co oznacza, że stwierdzenie jest możliwe do udowodnienia), co prowadzi do sprzeczności, dlatego P = NP powinno być możliwe do udowodnienia .

Brzmi to dla mnie jako dowód na udowodnienie, że P = NP, ale myślę, że jest bardzo prawdopodobne, że wynika to z mojego niezrozumienia związanych z tym zagadnień logicznych. Czy ktoś mógłby mi pomóc zrozumieć, co jest z tym nie tak?

np-hardness proofs p-vs-np

— Alvaro
źródło

Zobacz artykuł Scotta Aaronsona „Czy P kontra NP jest formalnie niezależny?”

— Marzio De Biasi

Wydaje mi się, że masz bardziej podstawowe zamieszanie co do tego, jak coś może być prawdziwe, ale nie do udowodnienia. Sprawdź przewodnik i centrum pomocy dotyczące zakresu tej witryny. Myślę, że to bardziej nadaje się do informatyki lub matematyki .

— Kaveh

ten semifamous papier Naturalne dowody autorstwa Razborova / Rudicha można zastosować do tego pytania

— wzn

Może Cię również zainteresować monografia Hartmanisa „Wykonalne obliczenia i możliwe do udowodnienia właściwości złożoności”, która zasadniczo omawia to, co się stanie, jeśli weźmiemy pod uwagę tylko problemy, które można udowodnić w P, możliwe w NP itp.

— Joshua Grochow

Odpowiedzi:

Jeśli P = NP, muszą istnieć algorytmy wielomianowe dla problemów z NP-zupełnym. Jednak może nie istnieć żaden algorytm, który mógłby rozwiązać problem NP-zupełny i działałby w czasie wielomianowym.

— David Richerby
źródło

Więc mówisz, że wadą jest to, że może istnieć przykład rozwiązania wielomianowego, ale możesz nie być w stanie udowodnić, że jest to wielomian? Ponieważ wtedy nie jest to brane pod uwagę w przykładzie, więc wciąż nie widzę wady.

— Alvaro

Załóżmy, że P = NP, ale nie da się tego udowodnić. Oznacza to, że istnieje algorytm wielomianowy A dla 3-SAT. Gdyby można udowodnić, że A był algorytmem wieloczasowym dla 3-SAT, byłoby to sprzeczne z niemożnością udowodnienia P = NP. Dlatego chociaż prawdą jest, że A działa w czasie wielomianowym i że A rozwiązuje 3-SAT, co najmniej jednego z tych faktów nie można udowodnić. Aby sformułować to w kategoriach pytania, faktem jest, że algorytm wielogodzinny dla 3-SAT istnieje nie oznacza, że można go „znaleźć”.

— David Richerby

Zatem „Ale jeśli nie można znaleźć przykładu rozwiązania wielomianu dla problemu NP-zupełnego, oznacza to, że P = NP jest fałszywe” jest błędne, ponieważ może istnieć rozwiązanie, nawet jeśli nie można go znaleźć?

— Alvaro

To jest poprawne.

— David Richerby

M

$M$

c

$c$

N

$N$

n \geq N

$n \geq N$

n

$n$

M

$M$

n^{c}

$n^c$

$\neq$

— Tpecatte
źródło