5
$\begingroup$

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.

EDIT 2:

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ If $A$ is an incomplete set in $NP$ then the complement of $A$ is incomplete in $coNP$. $\endgroup$
    – Mohammad Al-Turkistany
    May 17, 2015 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, 2015 at 15:33
  • $\begingroup$ @WillSawin What is the strongest known complexity theoretic assumption? $\endgroup$
    – Mohammad Al-Turkistany
    Jun 4, 2015 at 20:44

0

Reset to default

Your Answer

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