Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for $NP$.

For instance, the theory should explain why problems with polynomially bounded solutions (FewP) can not be complete. Also, it should explain why problems solvable by bounded nondeterminism (log-clique) can not be complete.

Is there a research program that tries to link the apparent incompleteness of at least two candidate problems in Suresh's post? What are the obstacles to such program?

EDIT I am also interested in published research studying the connection between incomplete sets for $NP$ and finite versions of Godel's 2nd incompleteness theorem in the context of proof complexity.

Posted on TCS SE.


Some of the results in Suresh's post can be interpreted as (conjectured) necessary conditions for the $NP$-completeness of a given problem $B$:

1- Problem B must be exponentially dense.

2- Problem B can have exponential number of solutions.

3- Problem B must require linear nondeterministic bits to solve.

  • $\begingroup$ If $A$ is an incomplete set in $NP$ then the complement of $A$ is incomplete in $coNP$. $\endgroup$ – Mohammad Al-Turkistany May 17 '15 at 0:01
  • 1
    $\begingroup$ Clearly one can only hope for results conditional on complexity-theoretic assumptions, because any result of this type implies $P \neq NP$. In fact one might have to assume something significantly stronger than $P\neq NP$. $\endgroup$ – Will Sawin Jun 4 '15 at 15:33
  • $\begingroup$ @WillSawin What is the strongest known complexity theoretic assumption? $\endgroup$ – Mohammad Al-Turkistany Jun 4 '15 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.