2
$\begingroup$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages in NP reduce to in polynomial time.

But is this idea that NP-completeness implies all problems are in P if they are in P all encompassing? Of course, it works for other problems in NP, but let's take a problem in, say, EXPTIME, which P is known to be a proper subset of.

Is it correct to say that there is a polynomial time reduction from a language $A$ and a language $B$ in EXPTIME, if and only if $B \in P \Rightarrow A \in P$? How about the inverse? $B$ (in EXPTIME) reduces to $A$ iff $A \in P \Rightarrow B \in P$? And of course, what about the general case?

$\endgroup$
1
  • $\begingroup$ Also note: I am talking about Turing reductions in polytime. $\endgroup$
    – Ank i zle
    Apr 14, 2023 at 5:22

1 Answer 1

3
$\begingroup$

No, this only works one way.

If there is a polynomial time reduction from $A$ to $B$, then $B \in P \implies A \in P$. This works irrespective of the what kind of languages $A$ and $B$ are.

The converse is not true. For example, take two languages $A, B \notin P$ such that there is no polynomial time reduction from $A$ to $B$ (these exist by the time hierarchy theorem). Then it still holds that $B \in P \implies A \in P$, since both sides of the implication are false.

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