Skip to main content
Computer Science

Return to Answer

replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard?What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

added 34 characters in body
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

The answer depends on what you mean by the notation $\le_p$.

If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is Yes. It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know, but we think not". Let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

The answer depends on what you mean by the notation $\le_p$.

If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is Yes. It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know, but we think not". Let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

The answer depends on what you mean by the notation $\le_p$.

  • If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.

  • Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

    In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490