4 ms·
A few comments imply that this introduces the question of P ?= NP, and while it indeed is defining a complexity problem, this is about satisfiability of first o
by ot 8y ago
A few comments imply that this introduces the question of P ?= NP, and while it indeed is defining a complexity problem, this is about satisfiability of first order predicates logic, that is formulas with sets and quantifiers, while SAT is about propositional logic.
First order logic was famously proved incomputable by Godel himself, so here he's asking whether we can bound the number of steps given the size of the proof, not the size of the input (formula length), which is the way complexity is usually defined.
In practice, he's saying that tractable theorems must have reasonably sized proofs (to be understood by a human), and there might be an algorithm that is efficient enough in finding short proofs.
- earthicus 8y agoAccording 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.
- deleted 8y ago[deleted]