In If P=NP, could we obtain proofs of Goldbach's Conjecture etc.? it talks about the hypothetical world where P=NP and using the proof of it to prove a problem/theorem assuming that it has a short proof.

But what exactly is the restriction imposed on problems/theorems? Do they have to be describable in $\Pi_1$ to use Levin's universal search?

If so, can the question like Navier-Stokes existence and smoothness problem be statble in $\Pi_1$?

  • 5
    $\begingroup$ The only thing that matters is that the given proof system (in this case, ZFC or similar) has polynomial-time recognizable proofs. The complexity of the statement being proved is irrelevant. $\endgroup$ Commented Jun 7, 2015 at 11:17
  • $\begingroup$ If downvoting, please also consider suggesting how you think the question could be improved. $\endgroup$
    – usul
    Commented Jun 8, 2015 at 18:30
  • $\begingroup$ @usul, I think the first part is answered by Emil's comment (I feel it was clear in the original post). The second part about logical complexity of stating a mathematical statement seems more suitable for Mathematics or MathOverflow. $\endgroup$
    – Kaveh
    Commented Jun 10, 2015 at 6:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.