13
$\begingroup$

First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course taken while I'm still an undergraduate), so this question may be very naive.

As far as I could find, the provability of P versus NP is an open problem.

Now:

  • Gödel's first incompleness theorem states that there may be statements that are true but not provable nor disprovable.
  • If a polynomial solution is found for an NP-complete problem, it proves that P = NP.

So, suppose that P=NP is not provable:
This means that no example of a polynomial solution for an NP-complete problem can be found (otherwise, this would be a proof).
But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false (proving it, meaning the statement is provable), which leads to a contradiction, therefore P=NP should be provable.

This sounds like a proof of the provability of P=NP to me, but I think it's extremely likely that it is due to my lack of understanding of the logic topics involved. Could anyone please help me understand what is wrong with this?

Improve this question
$\endgroup$
4
  • 12
    $\begingroup$ See Scott Aaronson's paper "Is P Versus NP Formally Independent?" $\endgroup$
    – Marzio De Biasi
    Commented Aug 29, 2013 at 12:32
  • 3
    $\begingroup$ It seems to be me that you have more basic confusion about how can something be true but unprovable. Please check tour and help center for the scope of this site. I think this is more suitable for Computer Science or Mathematics. $\endgroup$
    – Kaveh
    Commented Aug 29, 2013 at 22:48
  • $\begingroup$ this semifamous paper Natural proofs by Razborov/Rudich is applicable to this question $\endgroup$
    – vzn
    Commented Sep 2, 2013 at 15:59
  • $\begingroup$ You may also be interested in Hartmanis' monograph "Feasible Computations and Provable Complexity Properties" which essentially discusses what happens if we only consider problems that are provably in P, provably in NP, etc. $\endgroup$
    – Joshua Grochow
    Commented Sep 4, 2013 at 13:31

2 Answers 2

Reset to default
23
$\begingroup$

If P=NP, there must be polynomial-time algorithms for NP-complete problems. However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ So, what you are saying, is that the flaw is that there may be an example of a polynomial solution but you may not be able to prove that it is polynomial? Because then it is not considered in the proof by example, so I still don't see the flaw. $\endgroup$
    – Alvaro
    Commented Aug 29, 2013 at 18:25
  • 3
    $\begingroup$ Suppose that P=NP but this is not provable. This means there is a polynomial time algorithm A for 3-SAT. If you could prove that A was a poly-time algorithm for 3-SAT, that would contradict unprovability of P=NP. Therefore, although it is true that A runs in polynomial time and true that A solves 3-SAT, at least one of these facts cannot be proven.To phrase it in the terms of the question, the fact that a poly-time algorithm for 3-SAT exists does not imply that one "can be found". $\endgroup$
    – David Richerby
    Commented Aug 29, 2013 at 18:50
  • $\begingroup$ So, the "But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false" is wrong, because there can be a solution even though it cannot be found? $\endgroup$
    – Alvaro
    Commented Aug 29, 2013 at 18:55
  • $\begingroup$ That's correct. $\endgroup$
    – David Richerby
    Commented Aug 29, 2013 at 19:19
  • 3
    $\begingroup$ You may want to think about what "can be found" means. while you can enumerate over all turing machines, for each machine $M$ you'd have to show that: there exists an integer $c$ and an integer $N$, such that for all integers $n \geq N$ and all inputs of size $n$, $M$ runs in time at most $n^c$ and decides 3SAT. statements like this are in general not decidable. $\endgroup$
    – Sasho Nikolov
    Commented Aug 29, 2013 at 19:35
6
$\begingroup$

Gödel's incompleteness theorem is really about provability given a theory with enough expressive power, you'll end up with some statement which can be true in some models, and false in others, hence not provable. In this case, if P vs NP can't be proved, if you believe that reality is a model of mathematics, P = NP or P $\neq$ NP must still be true in "our world". Hence, as David said, either no polynomial algorithm exists but we won't be able to prove this statement, or a polynomial algorithm does exist but we won't be able to prove that it solves the problem or that it runs in polynomial time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.