# Are there problems in NP that would solve P vs NP, but are not NP complete

NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is if we were to find some polynomial time algorithm to solve one of these problems, we could prove $$P = NP$$. And if we could prove that no polynomial time algorithm could exist, this implies $$P \neq NP$$.

Are there other problems in $$NP$$ that have this property? That is,

Is it possible for a problem $$X$$ in $$NP$$ to not be NP-complete, but we could still solve $$P$$ vs. $$NP$$ by determining if it has polynomial time lower bounds.

Of course, proving that there is an exponential lower bound on any NP problem proves $$P \neq NP$$, but are there problems in NP where finding a polynomial time lower bound (besides NP complete problems) shows $$P = NP$$?

• Did you mean to write $\mathsf P \neq \mathsf{NP}$ in your last sentence? Commented Apr 7, 2023 at 9:25
• @Watercrystal I'm asking for something more along the lines of a class of problems that act like NP-complete problems, where if you find a polynomial time solution to them, you can prove $P = NP$. If you show exponential lower bounds on problems in this class, then $P \neq NP$, yes. But that is true for any problem in $NP$. I think my comment makes sense, please let me know if I am not being clear. Thanks. Commented Apr 7, 2023 at 9:44
• I think this analogy might be clearer actually: If one found a solution to graph isomorphism, that would not prove $P$ = $NP$. But if one were to find a solution to SAT, that would prove $P$ = $NP$. Is there a problem that is not NP-complete that has this same property of proving $P = NP$? Commented Apr 7, 2023 at 9:58
• If $GI \notin P$, then $P \neq NP$. Commented Apr 7, 2023 at 11:39
• @PålGD yes, but I’m asking for problems that satisfy the inverse. A problem $X$, such that $X \in P$ then $P = NP$. Commented Apr 7, 2023 at 17:43

Yes.

Ladner's theorem shows that for any problem $$X \in \mathrm{NP} \setminus \mathrm{P}$$ there is a problem $$Y \in \mathrm{NP} \setminus \mathrm{P}$$ such that $$Y$$ is reducible to $$X$$ but not vice versa.

If we apply the construction from Ladner's theorem to e.g. $$\mathrm{SAT}$$ we obtain a problem $$Z \in \mathrm{NP}$$ such that either $$Z$$ is neither in $$\mathrm{P}$$ nor $$\mathrm{NP}$$-complete (in case that $$\mathrm{P} \neq \mathrm{NP}$$); or $$Z$$ is simulatenously in $$\mathrm{P}$$ and $$\mathrm{NP}$$-complete (if $$\mathrm{P} = \mathrm{NP}$$).

In other words $$Z$$ is not $$\mathrm{NP}$$-complete unless for trivial reasons, and proving that $$Z$$ belongs to $$\mathrm{P}$$ entails $$\mathrm{P} = \mathrm{NP}$$.

To extend the answer provided by @Arno, the problems sought by the OP are those belonging to the class of NP-intermediate problems: $$N P I=N P \backslash(P \cup N P C)$$. Despite the interest, we still do not know of any natural problem belonging to this class, all we have are natural candidates, e.g. graph isomorphism, discrete logarithm and factoring. A few years ago I have found, along with my coauthor, another possible candidate which has been useful for the construction of a cryptographic protocol:

Exponentiating Polynomial Root Problem (EPRP)

Let $$p(x)$$ be a polynomial with $$deg(p) \geq 0$$ with coefficients drawn from a finite field $$GF(q)$$, and $$r$$ a primitive element for that field. Then, the problem of finding roots of

$$p(x) = r^x$$

is believed to be NP–intermediate, i.e., it is in the complexity class NP but it is supposed not to be in P nor NP–complete.

This problem is at least as hard as the discrete logarithm, it can be regarded as a generalization of it since the discrete logarithm problem is a particular case of EPRP when $$deg(p) = 0$$. Additional details can be found here or here.

• But would proving ERP to be polytime lead to the conclusion that $\mathrm{P} = \mathrm{NP}$?
– Arno
Commented Mar 13 at 8:28

My original answer below takes "not $$\mathsf{NP}$$-complete" in the OP's title and text at face value. As far as I can tell it is correct, and not incompatible with Arno's answer, whose interpretation of "not $$\mathsf{NP}$$-complete" is less "strict" — though probably closer to what the OP wanted and yielding more interesting properties!

Consider a problem $$X$$ in $$\mathsf{NP}$$ that is not $$\mathsf{NP}$$-complete. Suppose that finding out some bound on the complexity of $$X$$ would show $$\mathsf{P}=\mathsf{NP}$$.
The thing is that if $$\mathsf{P}=\mathsf{NP}$$, then all problems in $$\mathsf{NP}$$ are $$\mathsf{NP}$$-complete, except for the two trivial problems “always yes” and “always no”.
So $$X$$ would have to be either “always yes” or “always no”, whose complexity is well-known (they are constant time) and has no bearing on the $$\mathsf{P}$$ vs $$\mathsf{NP}$$ problem.
• Technically this answer is correct. If P=NP, then all problems in NP (except $\emptyset$ and $\Sigma^*$) are NP-complete, so the only candidates for $X$ in OP's question would be $\emptyset$ and $\Sigma^*$, which are already known to be in time $O(1)$. So, in the case P=NP, there are no problems of the kind OP asks for. I think for this reason OP's question, as worded, is not what OP actually intends to ask. Presumably, OP's intended question is more like this: are there problems that are now known to be in NP, but not currently known to be NP-complete, such that ....? Commented Apr 9 at 13:37