5
$\begingroup$

I was just wondering? Or if anyone knows any work relating the two? Also a negative result? Here CH is continuum hypothesis.

$\endgroup$
  • $\begingroup$ Do you have any remaining questions about Andres' answer? $\endgroup$ – Noah Schweber May 2 at 14:18
6
$\begingroup$

P=NP is an arithmetic statement: we can code the relevant deterministic Turing machines by numbers in a fairly explicit recursive way (which also explicitly involves codes for polynomial upper bounds), and then the equality between both classes can be discussed by discussing numerical properties of the indices involved in the coding, and using a specific NP-complete problem, such as 3SAT. The usual formalization shows that "P=NP" can be described by a statement about natural numbers of the form $\exists n\,\forall m\,\varphi(n,m)$ where all quantifiers in $\varphi$ are bounded.

The status of CH is completely independent of such statements: Cohen's forcing technique for modifying models of set theory allows us to go from a model $M$ to a model $M[G]$ some of whose properties we control. The technique never changes arithmetic statements. With forcing we can obtain models of CH and models of its negation.

Thus, if assuming CH (or its negation) allows us to prove (or to disprove) P=NP, the same can be accomplished without this assumption. And assuming P=NP (or its negation) does not allow us to prove (or to disprove) CH, unless we are in the silly situation where ZFC, the standard system for set theory, is itself inconsistent, or it is consistent and (say) proves P=NP, and yet we assume P$\ne$NP (or vice versa). In that silly scenario then we can prove CH. And its negation. (Because inconsistent theories prove everything.)

$\endgroup$
  • $\begingroup$ Technically, regarding the last sentence, if P=/=NP is provable in ZFC, then assuming P=NP we can prove CH... $\endgroup$ – Wojowu Apr 13 at 13:23
  • 2
    $\begingroup$ +1. More generally, OP, you may be interested in absoluteness results which give purely syntactic conditions according to which a given sentence can't depend on principles like CH, AC, etc. $\endgroup$ – Noah Schweber Apr 13 at 13:25
  • $\begingroup$ @Wojowu Hehe, yes, sorry, I edited the end accordingly. $\endgroup$ – Andrés E. Caicedo Apr 13 at 13:29
  • $\begingroup$ I read on wikipedia article you linked- "Many famous open problems, such as the Riemann hypothesis and the P = NP problem ... and thus cannot be proven independent of ZFC by forcing". Which if CH is shown to be independent of ZFC, a well know result now I suppose? So you have CH independent of ZFC, and P=NP not able to be shown independent of ZFC (at least by forcing), is then suggestive that ZFC and P=NP are not dependent (or still maybe nothing can be shown as to the their dependence)? Or at least intuitively P=NP more complex a situation? $\endgroup$ – marshal craft Apr 15 at 15:57
  • 1
    $\begingroup$ @marshal It has been known for over 50 years now that CH is independent of ZFC. This uses Cohen's method of forcing. The fact that arithmetic problems cannot be shown independent of ZFC by forcing is a limitation of the method, but really does not say much if anything about the problems themselves. $\endgroup$ – Andrés E. Caicedo Apr 15 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.