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 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.
 A: 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.
A: 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
A: 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
A: "This version of Levin's universal search algorithm solves SUBSET-SUM in polynomial time" is equivalent to P=NP.
A: 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.
