# Could P=NP be dependent with CH?

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

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

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.)