Graduate P vs NP & Godel | A Comprehensive Guide

[edmund cavendish]

TL;DR

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.

 

[Office_Shredder]

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?

 

[fresh_42]

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]

S. Aaronson, Is P versus NP formally independent (2003) might be of interest.
Link to the article.

Your question is difficult to understand. Are you asking whether the two are related somehow? E.g can diagonalisation be used to attack P vs NP? (as it can be for Gödel's theorems). The answer in that case is no due to the Baker-Gill-Solovay theorem. (also covered in Aaronson)

 

[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

 

[fresh_42]

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.

 

[fresh_42]

For those who are interested in a better but still simple description of P vs. NP, see
https://www.physicsforums.com/insights/p-vs-np-conjecture-calculations-and-meaning/