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.