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 '15 at 16:35
  • 1
    $\begingroup$ @kaveh Here we want the connection between two completely different NPI problems. $\endgroup$ – Mohammad Al-Turkistany Apr 22 '15 at 16:46
  • 1
    $\begingroup$ agreed with K, this is basically the study of the NPI "class" $\endgroup$ – vzn Apr 22 '15 at 17:49
  • 1
    $\begingroup$ NP-Incomplete = NPI union P $\endgroup$ – Tyson Williams Apr 23 '15 at 12:31
  • 1
    $\begingroup$ @TysonWilliams Yes, that is correct. $\endgroup$ – Mohammad Al-Turkistany Apr 23 '15 at 13:16

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.