<p>Motivated by Suresh's post, <a href="https://cstheory.stackexchange.com/questions/20883/techniques-for-showing-that-problem-is-in-hardness-limbo/20891">Techniques for showing that problem is in hardness limbo</a>, it seems that there might be an underlying theory that explains why some of these problems can <strong>not</strong> be complete for $NP$.</p>

<p>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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p><strong>EDIT</strong>: 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 <a href="https://mathoverflow.net/questions/206807/is-there-a-program-for-theory-of-incompleteness-in-np">MathOverflow</a>.</p>

<p><strong>EDIT 2</strong>:</p>

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

<p>1- Problem B must be exponentially dense.</p>

<p>2- Problem B can have exponential number of solutions.</p>

<p>3- Problem B must require linear nondeterministic bits to solve.</p>

CC BY-SA 3.0
2015-04-22T16:35:48.070Z
Wasn't there a question about "NPI-complete"?
Kaveh
CC BY-SA 3.0
2015-04-22T16:46:29.517Z
@kaveh Here we want the connection between two completely different NPI problems.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-04-22T17:49:43.987Z
agreed with K, this is basically the study of the [NPI](http://cstheory.stackexchange.com/search?q=npi+is%3Aquestion) "class"
vzn
CC BY-SA 3.0
2015-04-23T12:31:59.833Z
NP-Incomplete = NPI union P
Tyson Williams
CC BY-SA 3.0
2015-04-23T13:16:56.947Z
@TysonWilliams Yes, that is correct.
Mohammad Al-Turkistany
<cc.complexity-theory>
Is there a program for theory of incompleteness in $NP$?
Mohammad Al-Turkistany
# Is there a program for theory of incompleteness in $NP$?

(Asked by: username_0 on 2015-04-22)

Motivated by Suresh's post, [Techniques for showing that problem is in hardness limbo](https://cstheory.stackexchange.com/questions/20883/techniques-for-showing-that-problem-is-in-hardness-limbo/20891), 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](https://mathoverflow.net/questions/206807/is-there-a-program-for-theory-of-incompleteness-in-np).

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

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Wasn't there a question about "NPI-complete"?  
> **username_0**: @kaveh Here we want the connection between two completely different NPI problems.  
> **username_2**: agreed with K, this is basically the study of the [NPI](http://cstheory.stackexchange.com/search?q=npi+is%3Aquestion) "class"  
> **username_3**: NP-Incomplete = NPI union P  
> **username_0**: @TysonWilliams Yes, that is correct.  

---

## 0 answers

