3
$\begingroup$

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$?

$\endgroup$
6
  • $\begingroup$ Did you mean to write $\mathsf P \neq \mathsf{NP}$ in your last sentence? $\endgroup$ Commented Apr 7, 2023 at 9:25
  • $\begingroup$ @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. $\endgroup$
    – Loic Stoic
    Commented Apr 7, 2023 at 9:44
  • $\begingroup$ 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$? $\endgroup$
    – Loic Stoic
    Commented Apr 7, 2023 at 9:58
  • 1
    $\begingroup$ If $GI \notin P$, then $P \neq NP$. $\endgroup$
    – Pål GD
    Commented Apr 7, 2023 at 11:39
  • $\begingroup$ @PålGD yes, but I’m asking for problems that satisfy the inverse. A problem $X$, such that $X \in P$ then $P = NP$. $\endgroup$
    – Loic Stoic
    Commented Apr 7, 2023 at 17:43

3 Answers 3

5
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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.

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

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!


The answer is no.

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.

$\endgroup$
3
  • $\begingroup$ This argument seems to assume that the only way the P vs. NP problem might be resolved, is to show that P = NP. What if finding out some bound on the complexity of X would show that P != NP? $\endgroup$
    – kaya3
    Commented Mar 13 at 15:42
  • $\begingroup$ @kaya3 the OP specifically asked for problems which would imply that P=NP. There are lots of problems for which finding an exponential lower bound would show that P≠NP, as the OP argues. $\endgroup$
    – lxnv
    Commented Mar 14 at 21:03
  • $\begingroup$ 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 ....? $\endgroup$
    – Neal Young
    Commented Apr 9 at 13:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.