Equivalent forms of the P vs. NP problem

Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral equality, etc.

I wonder about equivalent formulations of the N vs. NP problem. Formulations that are very much different from the questions such "Is TSP in P?", formulation that may seem unrelated to complexity theory.

There is the descriptive complexity formulation:

P = NP is equivalent to the statement that every property expressible by a second order existential statement is also expressible in first order logic with a least fixed point operator.

See, e.g., Immerman's survey here: https://people.cs.umass.edu/~immerman/pub/capture.pdf

• Presumably "expressible" here means "expressible in finite ordered structures"? – Andreas Blass May 8 '19 at 21:13

I think "Geometric Complexity Theory" is roughly speaking an attempt to do what you're talking about: formulate P vs. NP in very different language. See https://en.wikipedia.org/wiki/Geometric_complexity_theory. I think that technically it may be dealing with "VP vs. VNP" rather than "P vs. NP" but in spirit it fits your request.

The P vs NP problem can be formulated in terms of incomplete sets in NP. Ladner theorem can be stated as:

$$P \ne NP$$ if and only if there is an incomplete set in NP.

Incomplete set is a set that is not complete for $$NP$$ under many-one polynomial time reductions (Karp reductions).

Another formulation in terms of sparse sets is Mahaney's Theorem:

There is no sparse NP-complete set if and only if $$P \ne NP$$ (under Karp reduction).

Complexity Theory and Cryptology: An Introduction to Cryptocomplexity By Jörg Rothe, page 106

https://www.cs.toronto.edu/~sacook/homepage/ptime.pdf

The above paper (1991) gives a syntactic method for enumerating all the PTIME functions. P != NP is the proposition that none of the functions in that enumeration recognize 3SAT. That suggests various half-baked proof ideas that I'm sure lots of people have thought of, so they presumably don't work, though who knows.

"This version of Levin's universal search algorithm solves SUBSET-SUM in polynomial time" is equivalent to P=NP.