Hacker News Reader

According to [1], the question Goedel raises is equivalent to P vs NP, although clearly not phrased in the same language. The author claimes Goedel's phi(n) is polynomially bounded if and only if P=NP. Do you disagree with that statement?

[1] https://ecommons.cornell.edu/bitstream/handle/1813/6910/89-9...

View on HN

> The author claimes Goedel's phi(n) is polynomially bounded if and only if P=NP. Do you disagree with that statement?

It would be trivially true if Godel was talking about propositional logic (proof size is polinomially bounded by definition of NP).

I don't know if that's true for first order logic (it's not as obvious to me as the author seems to imply) but even in that case it would be a non-trivial connection, so I believe it's a stretch to say that this was about P and NP.

Reply on news.ycombinator.com