Skip to main content
clarify that last paragraph assumes that P ≠ NP
Source Link
ruakh
  • 713
  • 4
  • 10

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.

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, 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.

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.

Source Link
ruakh
  • 713
  • 4
  • 10

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, 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.