3 ms·
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
by earthicus 8y ago
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-994.pdf?sequence=1 https://ecommons.cornell.edu/bitstream/handle/1813/6910/89-9...
- ot 8y ago> 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.