P vs NP and Godel

edmund cavendish
TL;DR Summary
If P = NP are there implications for Godel's Incompleteness theoem, or is it just an instance of sonething that might be true but can't be proved true that now has been?
I think the essence is captured above.

Jarvis323
If P = NP are there implications for Godel's Incompleteness theoem,
No.
or is it just an instance of sonething that might be true but can't be proved true that now has been?
No. It would have plenty of profound implications, just not about incompleteness.

fresh_42
Staff Emeritus
Gold Member
P vs np is a statement about problems where we already know how to construct solutions, and just want to know if we can do it faster. So the content doesn't have anything to do with incompleteness.

I think in principle maybe p vs np could be undecidable, but this doesn't strike me as particularly likely - everything here is finite, so why should it depend on our choice of set theory? It would certainly be an interesting result that might teach us something deep about mathematics if it is.

The question is also a question of application, so if we somehow decided it could be true but could not be proven to be true, then it means we can't construct a useful algorithm and it might as well be false.

edmund cavendish
Thank you. I was thinking specifically about Godels idea of truths in mathematics that existed but couldn't be proved to exist proving one of this categiry to be true may simply leave that set at n minus one, but could there ever be anything in the solving of one instance that did more than just affect that one instance?

Mentor
2022 Award
The question is also a question of application, so if we somehow decided it could be true but could not be proven to be true, then it means we can't construct a useful algorithm and it might as well be false.
I am quite certain that ##P \neq NP## will be proven someday. Finding an appropriate lower bound, however, could be NP-hard . It is basically a proof about the lack of a certain solution which is system immanently harder than finding one.

##P=NP##, on the other hand, with a translation algorithm of, say ##O(N^{10^{(10^{30})}}),## would be cool, extremely ugly, but cool.

nuuskur
Last edited:
fresh_42
edmund cavendish
Thank you. I was really pondering whether any number of godels unprovable but existing truths that might be proved has any effect on his theorem, in the same way as whether however many instances in Riemann or Goldbach are proved brings us no nearer an absolute answer than when we had one instance? Is it all or nothing?
Thanks

Mentor
2022 Award
Riemann and Goldbach are problems in number theory. They both deal in a wider sense with the question of whether there are enough prime numbers.

P=NP is a problem about computation classes. The question behind it is whether there are intrinsic hard problems or whether we are just not capable to find smart solutions.

Goedel is pure logic and as far as I know a pure existence theorem.

None of the three has anything to do with the other. To connect them rigorously would require a fair amount of work.