11
$\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 ?

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ Have you read en.wikipedia.org/wiki/… ? $\endgroup$
    – Jukka Suomela
    Commented Aug 27, 2010 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
    Commented Aug 27, 2010 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
    Commented Aug 27, 2010 at 21:05
  • $\begingroup$ @Monoid, you should reword your question to reflect this clarification then. As such the question is ambiguous $\endgroup$
    – Suresh Venkat
    Commented Aug 27, 2010 at 22:01
  • $\begingroup$ possible duplicate of Many-one reductions vs. Turing reductions to define NPC $\endgroup$
    – Suresh Venkat
    Commented Aug 28, 2010 at 6:15

6 Answers 6

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 27, 2010 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
    Commented Aug 29, 2010 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
    Commented Aug 29, 2010 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.

Improve this answer
$\endgroup$
9
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ link does not work. $\endgroup$
    – Turbo
    Commented May 5, 2016 at 23:06
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 26, 2010 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
    Commented Nov 27, 2010 at 17:07
  • $\begingroup$ I assume you only mean natural NPC problems, otherwise the NPC solver can request a correct hash input $\endgroup$
    – l4m2
    Commented Dec 29, 2022 at 17:41
5
$\begingroup$

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

Improve this answer
$\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" .

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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