<p>I think what you are looking for is the notion of polynomial-time Turing reduction, denoted $\leq_{T}^{p}$ (also called Cook reduction, since this was the notion of reduction Cook used in the paper in which he defined NP-completeness; poly-time many-one reductions are called "Karp" or "Karp-Levin" for a similar reason), or polynomial-time truth-table reductions, denoted $\leq_{tt}^{p}$.</p>

<p>For any notion of reduction, you get a notion of NP-completeness: e.g. a problem is "NP-complete under $\leq_{T}^{p}$ reductions" if it is in NP and every problem in NP $\leq_{T}^{p}$-reduces to it.  The different notions of completeness are a priori distinct; however, even if they are distinct, showing that a problem is NP-complete under Cook reductions is still good evidence of its intractability.</p>

<p>Terminologically, when people say "NP-complete" without further specifying, they usually mean NP-complete under many-one reductions.</p>

<p><a href="http://dx.doi.org/10.1016/0304-3975(95)00189-1" rel="nofollow">Lutz and Mayordomo</a> showed that if NP does not have measure 0 in EXP,  there are problems that are NP-complete under $\leq_{T}^{p}$-reductions that are not NP-complete under $\leq_{m}^{p}$-reductions. The Lutz and Mayordomo paper has lots of other references, but one result that should be mentioned is that (under no assumptions), there are problems that are  $\leq_{T}^{p}$-complete for $NE$ that are not $\leq_{m}^{p}$-complete for $NE$ [1,2].</p>

<p>Truth-table reductions can be viewed either as a multi-query version of many-one reductions (in a sense they are "many-many") or as non-adaptive Turing reductions, or as Turing reductions in which all the queries are made in parallel.  The idea is that the reducing machine looks at the input, decides all the queries it's going to make without asking any of them, then asks all of them and gets answers from the oracle, then decides its answer without making further queries.</p>

<p>[1] H. Buhrman, S. Homer and L. Torenvliet, Completeness for nondeterministic complexity classes, Math. Systems Theory 24 (1991) 179-200.</p>

<p>[2] O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987.</p>

CC BY-SA 2.5
2010-12-01T15:43:23.597Z
2010-12-01T15:43:23.597Z
Joshua Grochow
<p>For proving a decision problem is NP-com, there are diffrent methods of reductions as parsimonious, like karp-reduction, or many-to-one reductions!
What about one-to-many map? is it possible to set a polynomial one-to-many reduction from NP-comp decision problem 'A' to a decision problem 'B' which we are looking for it's complexity? </p>

CC BY-SA 2.5
2010-12-01T15:14:04.380Z
What is a one-to-many map?
Robin Kothari
CC BY-SA 2.5
2010-12-01T15:36:50.487Z
In addition to Robin’s question, I do not think that “Is it allowed to use …?” is the right question.  Of course you are _allowed_ to use anything as long as it is well-defined.  What really matters is whether it is interesting, useful, and so on, in certain context or for certain purpose.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-01T16:33:49.710Z
Assume there is a NP-comp problem 'A' and we are looking for the complexity of decision problem 'B' and we chould find a polynomial  map which tansforms each instace of 'A' to more than one instance of 'B'! can someone conclude that 'B' is also NP-comp?
marjoonjan
CC BY-SA 2.5
2010-12-01T18:32:33.860Z
(1) It is better to update the question to clarify the meaning rather than adding comments.  (2) When doing so, please clarify what you mean by transforming an instance of A to more than one instance of B.  Of course, you can transform one thing to another as you like, but that is not necessarily a reduction because the reduction must preserve the answer.  When transforming one thing to many things, I do not know what “preserve the answer” would mean.
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes>
can some one use a polynomial one-to-many reduction for NP-comp problems?
marjoonjan
# can some one use a polynomial one-to-many reduction for NP-comp problems?

(Asked by: username_0 on 2010-12-01)

For proving a decision problem is NP-com, there are diffrent methods of reductions as parsimonious, like karp-reduction, or many-to-one reductions!
What about one-to-many map? is it possible to set a polynomial one-to-many reduction from NP-comp decision problem 'A' to a decision problem 'B' which we are looking for it's complexity?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: What is a one-to-many map?  
> **username_2**: In addition to Robin’s question, I do not think that “Is it allowed to use …?” is the right question.  Of course you are _allowed_ to use anything as long as it is well-defined.  What really matters is whether it is interesting, useful, and so on, in certain context or for certain purpose.  
> **username_0**: Assume there is a NP-comp problem 'A' and we are looking for the complexity of decision problem 'B' and we chould find a polynomial  map which tansforms each instace of 'A' to more than one instance of 'B'! can someone conclude that 'B' is also NP-comp?  
> **username_2**: (1) It is better to update the question to clarify the meaning rather than adding comments.  (2) When doing so, please clarify what you mean by transforming an instance of A to more than one instance of B.  Of course, you can transform one thing to another as you like, but that is not necessarily a reduction because the reduction must preserve the answer.  When transforming one thing to many things, I do not know what “preserve the answer” would mean.  

---

## 1 answers

### Answer by username_3 on 2010-12-01. Score: 13 | Accepted answer

I think what you are looking for is the notion of polynomial-time Turing reduction, denoted $\leq\_{T}^{p}$ (also called Cook reduction, since this was the notion of reduction Cook used in the paper in which he defined NP-completeness; poly-time many-one reductions are called "Karp" or "Karp-Levin" for a similar reason), or polynomial-time truth-table reductions, denoted $\leq\_{tt}^{p}$.

For any notion of reduction, you get a notion of NP-completeness: e.g. a problem is "NP-complete under $\leq\_{T}^{p}$ reductions" if it is in NP and every problem in NP $\leq\_{T}^{p}$-reduces to it. The different notions of completeness are a priori distinct; however, even if they are distinct, showing that a problem is NP-complete under Cook reductions is still good evidence of its intractability.

Terminologically, when people say "NP-complete" without further specifying, they usually mean NP-complete under many-one reductions.

[Lutz and Mayordomo](http://dx.doi.org/10.1016/0304-3975(95)00189-1) showed that if NP does not have measure 0 in EXP, there are problems that are NP-complete under $\leq\_{T}^{p}$-reductions that are not NP-complete under $\leq\_{m}^{p}$-reductions. The Lutz and Mayordomo paper has lots of other references, but one result that should be mentioned is that (under no assumptions), there are problems that are $\leq\_{T}^{p}$-complete for $NE$ that are not $\leq\_{m}^{p}$-complete for $NE$ [1,2].

Truth-table reductions can be viewed either as a multi-query version of many-one reductions (in a sense they are "many-many") or as non-adaptive Turing reductions, or as Turing reductions in which all the queries are made in parallel. The idea is that the reducing machine looks at the input, decides all the queries it's going to make without asking any of them, then asks all of them and gets answers from the oracle, then decides its answer without making further queries.

[1] H. Buhrman, S. Homer and L. Torenvliet, Completeness for nondeterministic complexity classes, Math. Systems Theory 24 (1991) 179-200.

[2] O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987.


---

