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?

  • 4
    $\begingroup$ What is a one-to-many map? $\endgroup$ Dec 1 '10 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 1 '10 at 15:36
  • $\begingroup$ 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? $\endgroup$
    – marjoonjan
    Dec 1 '10 at 16:33
  • 1
    $\begingroup$ (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. $\endgroup$ Dec 1 '10 at 18:32

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.