1
$\begingroup$

Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving the existence of incomplete sets in R.E. using diagonalization method.

Reductions in complexity theory are the resource bounded versions of many-one and Turing reductions of computability theory. Also, the standard notion of efficient algorithms is the resource bounded version of Turing machines. Completeness is defined using Karp reduction (polynomial time many-one reduction).

Although that served us very well into classifying problems into intractable NP-complete problems and efficiently solvable ones, the analogue breaks down when it comes to natural incomplete problems inside R.E. and NP.

As far as I know, there are no known natural intermediate (incomplete) problems between R.E. degree and Recursive degree. We were only able to prove the existence of artificial problems with intermediate degrees. In contrast in complexity theory, we have plenty of intermediate problems. This post, Techniques for showing that problem is in hardness “limbo” , shows that are plenty of natural intermediate (conjectured to be incomplete) sets inside NP. It is known that $ P \ne NP$ if and only if there exists an incomplete set in $NP$.

What evidence do we have to supports the belief that current theory of NP-completeness can not prove the existence of incomplete sets in NP? Does the situation change if we use weaker reductions such as logspace many-one or $AC^0$ instead of Karp reduction?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Well, the existence of incomplete sets in NP immediately implies P$\not=$NP, so your question boils down to what evidence we have that current complexity theory can't resolve P vs. NP. For this, I'd point to the standard obstacles: that no relativizing or natural proof can work; these types of argument encompass the vast majority of arguments we know how to do.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is the converse $P\neq NP\implies$ incomplete sets in $NP$ possible? $\endgroup$
    – Turbo
    Dec 10, 2020 at 5:03
  • $\begingroup$ @1.. It's not only possible, it's Ladner's theorem. $\endgroup$
    – Noah Schweber
    Dec 10, 2020 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.