Is there any kind of connection between the Axiom of Choice and the $\rm P = NP$ problem?

Question

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

Answer 1

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