Equivalent forms of the P vs. NP problem

Question

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 am wondering about equivalent formulations of the P 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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.