1
$\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$
5
  • $\begingroup$ Did you mean to write $\mathsf P \neq \mathsf{NP}$ in your last sentence? $\endgroup$ 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
    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
    Apr 7, 2023 at 9:58
  • 1
    $\begingroup$ If $GI \notin P$, then $P \neq NP$. $\endgroup$
    – Pål GD
    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
    Apr 7, 2023 at 17:43

2 Answers 2

1
$\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$
-2
$\begingroup$

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$

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.