5
$\begingroup$

Possible Duplicates:
Do many-one reductions and Turing reductions define the same class NPC
Many-one reductions vs. Turing reductions to define NPC

Let $P,Q \subseteq \Sigma^*$ be languages such that $P$ and $Q$ are both in NP. Assume that $P$ is NP-complete under Karp reductions (there is a polynomial time many-one reduction from 3-SAT to $P$) and there is a Turing-reduction from $P$ to $Q$, i.e. there is a polynomial-time algorithm which decides $P$ when given oracle-access to $Q$. Intuitively this means that deciding $Q$ is as hard as deciding any problem in NP, while at the same time $Q$ is in NP, so Q cannot be ``harder'' than NP. Does this imply that $Q$ is NP-complete under Karp reductions, i.e. does this imply the existence of a polynomial-time many-one reduction from 3-SAT to Q? Any pointers are much appreciated.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ In summary: $\mathbf{3SAT} \ \le_m^\rm{P} \ \mathbf{P} \ \le_T^\rm{P} \ \mathbf{Q}$, where $\le_m^\rm{P}$ denotes polynomial-time many-one (Karp) reduction, and $\le_T^\rm{P}$ denotes polynomial-time Turing reduction. $\endgroup$
    – Sadeq Dousti
    Nov 26, 2010 at 14:27
  • 3
    $\begingroup$ Note that problem $P$ plays no real part in your question, you may as well replace it by SAT. $\endgroup$
    – András Salamon
    Nov 26, 2010 at 16:14
  • 1
    $\begingroup$ Don't close this question. It's a real question. I don't know the answer, and I don't believe anybody else has given the answer, either. $\endgroup$
    – Peter Shor
    Nov 26, 2010 at 17:03
  • 1
    $\begingroup$ @Peter: I know the definition of Turing reductions, but you have not explained why UNSAT is NP-complete under Turing reducibility. NP-completeness means that it belongs to NP and it is NP-hard. $\endgroup$
    – Tsuyoshi Ito
    Nov 26, 2010 at 17:32
  • 1
    $\begingroup$ I fixed the duplicate question cstheory.stackexchange.com/questions/686/… by changing it's wording, and now I feel O.K. about closing this one. $\endgroup$
    – Peter Shor
    Nov 27, 2010 at 12:46

0

Reset to default