I would like to ask this:

  • Does anybody know about some kind of paper/analysis/research/thesis/etc. which examines that whether there is any connection between the P = NP problem and accepting the Axiom of Choice as true or false (and use ZF+AC or ZF+$\neg$AC) or not?

I ask this question because recently I read the wikipedia page of the Axiom of Choice and found this in the section called "Statements consistent with the negation of AC":

...For certain models of ZF+$\neg$AC, it is possible to prove the negation of some standard facts... There exists a model of ZF+$\neg$AC in which real numbers are a countable union of countable sets

So, for me this means that it is possible that emerging of the cardinality of the continuum is based on we accept the Axiom of Choice as true or false. In that case is there any chance for the truthfullness of P = NP is based on how we accept the Axiom of Choice as well?

Thx for any reply!

Best regards

  • $\begingroup$ P vs NP has to do with finite things, and wheter something can be done quickly, and AC has to do with infinite things, and whether something can be done at all. Those are pretty different worlds, so my gut says "no". Although I'm not certain in any way. $\endgroup$ – Arthur Aug 30 '17 at 9:35
  • $\begingroup$ I agree with @Arthur, the precense of a choice function can in some cases be guaranteed without resorting to AC. For example there is always a choice function if the sets of the family are countable (not the same as countable choice). $\endgroup$ – skyking Aug 30 '17 at 9:41
  • 1
    $\begingroup$ Also the fact that if $P=NP$ it would mean that there actually is an algorithm that solves $NP$ problems in polynomial time. If there is such an algorithm that wouldn't be affected by whether we accept AC or not. $\endgroup$ – skyking Aug 30 '17 at 9:44
  • $\begingroup$ My gut feeling is that the axiom of choice or it's negation would at best turn the decidability of the question. $\endgroup$ – skyking Aug 30 '17 at 9:49

The comments point out that $\rm P=NP$ "has to do with finite things". But formally speaking, it is a statement about the natural numbers. It is a first-order statement about the natural numbers. And in fact not a very complicated one.

One can prove, quite easily once all the technical definitions had been understood, that the first-order theory of the natural numbers is the same in all the transitive models. And in particular, in $L$, Godel's constructible universe, where the axiom of choice holds.

So it follows that if $\rm P=NP$ holds in the universe, then it holds in all universes we can "reach", both with and without the axiom of choice.

What does that mean? It means that in order to change the truth value of a first-order statement about the natural numbers we need to change the natural numbers themselves. Specifically, we need to go to entirely different "type" of universes, where the notion of what are the natural numbers is somewhat different than what we started with. In particular, forcing-related methods are not going to be helpful in showing that $\rm P=NP$ is independent of $\sf ZF$.


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.