1
$\begingroup$

From my theory of computation lecture I recall:

If $A \le_m B$ and $B$ is decidable then $A$ is decidable (uses a computable function as a reduction).

If $A \le_p B$ and $B$ is in P then $A$ is in P (uses a polynomial function reduction).

I wanted to know if there is an analogous notion of reduction for the class NP.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The very same definition holds for NP as well. Take a look onlike at the class $NP-complete$, and somewhere there you should find about such reductions. $\endgroup$
    – nir shahar
    Commented Jul 27, 2021 at 13:37
  • $\begingroup$ @nirshahar if you mean the entry of wikipedia for np-completeness, section "Completeness under different types of reduction" then the different types of reductions yield different types (or at least not known to be equal) types of np-complete classes $\endgroup$
    – user1868607
    Commented Jul 27, 2021 at 13:55
  • $\begingroup$ The regular reduction definition still holds though, i.e $f:\Sigma^*\rightarrow \Sigma^*$ is said to be a poly reduction if it can be computed in poly time, and $x\in A\iff f(x)\in B$. I don't see a problem using this definition for languages in the NP class. Since the witness is in poly length, the reduction still works, and a similar property holds $\endgroup$
    – nir shahar
    Commented Jul 27, 2021 at 15:32
  • $\begingroup$ @nirshahar My question is about the most general reductions one can get. This holds indeed. What is the more general class of $f$ I can use, containing the polynomial reductions? $\endgroup$
    – user1868607
    Commented Jul 27, 2021 at 15:34
  • 1
    $\begingroup$ Does this answer your question? Proving that a problem is in NP $\endgroup$
    – idmean
    Commented Jul 28, 2021 at 5:36

1 Answer 1

Reset to default
1
$\begingroup$

Judging from your replies to nir shahar's comments above, it seems that you're really looking for a class of reduction functions that gives a necessary and sufficient condition, rather than merely a sufficient one as your question arguably implies.

If so, then the answer is rather boring: for any problem B in NP, a problem A is in NP if and only if it is nondeterministic-polynomial-time Turing-reducible to B, that is, if and only if there exists a Turing reduction from A to B that runs in polynomial time on a nondeterministic Turing machine, or (equivalently) that can be verified in polynomial time on a deterministic Turing machine.

I've specified Turing-reducible because a many-one reduction is not always available: if B is trivial (always returns "yes" or always returns "no"), and A is not, then there is no many-one reduction from A to B, regardless of whether A is in NP. However, if we require B to be non-trivial, then a nondeterministic-polynomial-time many-one reduction does have to exist. (Of course, there are other kinds of reductions besides Turing reductions and many-one reductions; but those are the most commonly discussed.)

Likewise, a polynomial-time reduction is not always available unless P = NP, because if B runs in polynomial time and A does not, then there won't be a polynomial-time reduction from A to B, regardless of whether A is in NP. However, if we require B to be NP-complete, then a polynomial-time reduction does have to exist, simply because that's the definition of NP-completeness.

Improve this answer
$\endgroup$
5
  • $\begingroup$ A reduction must be computable by a deterministic TM in polynomial time. Otherwise, NP-hard would make no sense. I could show that SAT can be reduced to binary search (as a decision problem). $\endgroup$
    – idmean
    Commented Jul 28, 2021 at 5:31
  • $\begingroup$ @idmean: I think you've misunderstood something (or else I am). SAT and binary search are both in NP, and the former cannot be reduced to the latter by a reduction that is "computable by a deterministic TM in polynomial time" unless it's true that P = NP. $\endgroup$
    – ruakh
    Commented Jul 28, 2021 at 5:37
  • $\begingroup$ After rereading I think I understand your premise, and there's nothing technically wrong. It's just a somewhat surprising and confusing definition. $\endgroup$
    – idmean
    Commented Jul 28, 2021 at 5:56
  • $\begingroup$ @idmean: It's not a definition, it's a (trivial) theorem. My understanding is that this theorem is what the question was asking for. Do you interpret the question differently? $\endgroup$
    – ruakh
    Commented Jul 28, 2021 at 6:03
  • $\begingroup$ i didn't read in depth in yet. but your first paragraph seems to interpret my question correctly $\endgroup$
    – user1868607
    Commented Jul 28, 2021 at 6:20

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.