11
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Presumably "expressible" here means "expressible in finite ordered structures"? $\endgroup$ – Andreas Blass May 8 '19 at 21:13
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.