10
$\begingroup$

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal.

Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class $C$ such as there exists a problem not in $C \cup co-C$ under Karp reduction and which is in $C$ under Turing reduction ?

$\endgroup$
  • 4
    $\begingroup$ Have you read en.wikipedia.org/wiki/… ? $\endgroup$ – Jukka Suomela Aug 27 '10 at 20:12
  • $\begingroup$ Thank you for your link. It answers to the first part of my question, but doesn't answers wether there are problems which arent in co-C under many-one reduction and are in C under Turing reduction, for any C. $\endgroup$ – Ludovic Patey Aug 27 '10 at 21:02
  • 1
    $\begingroup$ Sorry, this may seem an elementary question or maybe I am not thinking straight at this late hour but I am missing something in the wiki article. The article says that under Cook reductions, NP-complete is equal to co-NP-complete, but I don't see it. NP-hard is equal to co-NP-hard w.r.t Cook reductions, but NP-complete means being both NP-hard AND NP, and I don't see why (e.g.) TAUT would be in NP? I.e. TAUT is co-NP-hard under Cook reductions but that is not enough for being NP-complete. $\endgroup$ – Kaveh Aug 27 '10 at 21:05
  • $\begingroup$ @Monoid, you should reword your question to reflect this clarification then. As such the question is ambiguous $\endgroup$ – Suresh Venkat Aug 27 '10 at 22:01
  • $\begingroup$ possible duplicate of Many-one reductions vs. Turing reductions to define NPC $\endgroup$ – Suresh Venkat Aug 28 '10 at 6:15
5
$\begingroup$

Have a look at this this question and especially this answer by Aaron Sterling. In short: "they are conjectured to be distinct notions."

$\endgroup$
  • $\begingroup$ I know that if NP!=co-NP, they are distinct notions because Turing reduction collapses them, but could there be differences which wouldn't be collapses, for example a problem in NPI under many-one reduction and in NPC under Turing reduction ? $\endgroup$ – Ludovic Patey Aug 27 '10 at 20:56
  • $\begingroup$ @Monoïd: NP≠coNP does not imply (at least in an obvious way) that the two notions of reductions are distinct. I am afraid that you are confusing the class NP (which is defined independently of the choice of the notion of reductions) with the class of decision problems reducible to NP (which depends on the choice of the notion of reductions). $\endgroup$ – Tsuyoshi Ito Aug 29 '10 at 12:50
  • $\begingroup$ Oops, my previous comment was wrong. If NP≠coNP, the two notions of reductions are obviously distinct (SAT is unconditionally Turing reducible to UNSAT, but SAT is many-one reducible to UNSAT if and only if NP=coNP). $\endgroup$ – Tsuyoshi Ito Aug 29 '10 at 13:30
10
$\begingroup$

The "Boolean Hierarchy" BP is a whole hierarchy of combinations of NP problems under Karp reductions which are all in P^NP.

$\endgroup$
8
$\begingroup$

This doesn't answer your question, but one could ask the same question for weaker reductions. For example, does the set of NP-complete problems change if we permit only log space reductions, or only AC0 reductions, or even NC0 reductions. A suprising fact is that all known NP-complete problems are complete even with NC0 reductions.

Reference: Agrawal, M., Allender, E., and Rudich, S. 1997 Reductions in Circuit Complexity: an Isomorphism Theorem and a Gap Theorem.

$\endgroup$
  • $\begingroup$ Is this question about weaker reductions still open? If I have a problem which was NP complete under P/poly or BPP reductions, but apparently not under P reductions without assuming unproven number theoretic assumptions, is it worth making a note of? $\endgroup$ – Peter Shor Nov 26 '10 at 22:59
  • $\begingroup$ @Peter: In the paper I've cited, it is left open if there is any problem that is NP-complete under polynomial time reductions which isn't NP-complete under AC^0 reductions. This question has been answered by Reducing the complexity of reductions. They show a problem that is NP-complete with ACC reductions but not AC^0 reductions. None of these papers seem to comment on problems that are NP-complete under reductions stronger than polynomial time, and how that relates to the possibility of being NP-complete under polytime reductions. $\endgroup$ – Robin Kothari Nov 27 '10 at 17:07
8
$\begingroup$

As far as I can tell, this question really comprises two distinct questions, the first of which appears in the title and the second of which is given after the edit.

(1) Do many-one reductions and Turing reductions define the same set of NP-complete problems (i.e. problems that are both in NP and which SAT can be reduced to)? Whether NPC under Turing reductions is the same as NPC under many-one reductions was still an open problem seven years ago, and I don't believe it has been closed since. See this survey from the June 2003 ACM SIGACT News for details.

(2) What is the class of problems which SAT has a Turing reduction to, and vice versa? This is the class of NP-hard problems (under Turing reductions) which are in PNP. For more information on this, see Noam's answer.

$\endgroup$
  • $\begingroup$ link does not work. $\endgroup$ – Turbo May 5 '16 at 23:06
5
$\begingroup$

The two notions are different under some reasonable assumption. Please check this paper: http://www.cs.iastate.edu/~pavan/papers/reductions.pdf

$\endgroup$
1
$\begingroup$

This paper claims to show that the existence of a TFNEEXP problem that's
[sufficiently hard to solve with zero error in the worst-case] implies the existence of
"a Turing complete language for NP that is not truth-table complete for NP."

On the other hand, I haven't tried reading through any of their claimed proof for that result,
but Proposition 2 and/or its proof demonstrate(s) a misunderstanding of ZPP's definition:
It seems like they actually need ​ "FP can solve all of FZPP" , ​ rather than just ​ "ZPP = P" .

$\endgroup$

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.