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 MathOverflow.


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.

  • 1
    $\begingroup$ Wasn't there a question about "NPI-complete"? $\endgroup$
    – Kaveh
    Apr 22, 2015 at 16:35
  • 1
    $\begingroup$ @kaveh Here we want the connection between two completely different NPI problems. $\endgroup$ Apr 22, 2015 at 16:46
  • 1
    $\begingroup$ agreed with K, this is basically the study of the NPI "class" $\endgroup$
    – vzn
    Apr 22, 2015 at 17:49
  • 1
    $\begingroup$ NP-Incomplete = NPI union P $\endgroup$ Apr 23, 2015 at 12:31
  • 1
    $\begingroup$ @TysonWilliams Yes, that is correct. $\endgroup$ Apr 23, 2015 at 13:16


Your Answer

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

Browse other questions tagged or ask your own question.