The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a Karp reduction since there is no restriction on the number of calls to the oracle. So, I am interested in NP-complete graph problem that does not have a known Karp reduction from a NP-complete problem.

Is there a natural graph problem known to be $NP$-complete only under Cook reduction, but not known to be NP-complete under Karp reductions?

Naturalness should disallow specific features of feasible solutions, for otherwise it is quite easy to start from well-known problem and make it a little easier by allowing specific features.

  • $\begingroup$ "Known to be NP-compete only under Cook reductions" or "only known to be NP-complete under Cook reductions"? $\endgroup$ Dec 17 '13 at 21:05
  • 1
    $\begingroup$ NON-HAMILTONICITY. $\endgroup$ Dec 19 '13 at 5:38
  • 3
    $\begingroup$ @MohammadAl-Turkistany HAMILTONICITY is NP-complete, so we don't expect that NON-HAMILTONICITY be NP-complete (unless NP=coNP). However, it is NP-hard with respect to Cook reductions. Now I see that this doesn't fit your description, because the problem is not in NP. $\endgroup$ Dec 19 '13 at 16:06
  • 1
    $\begingroup$ See also this question: cstheory.stackexchange.com/questions/3333/…. $\endgroup$ Dec 19 '13 at 16:38
  • 3
    $\begingroup$ its a known open problem, basically. they are conjectured to be different, see lutz/mayordomo ref/answer for this question many one vs turing reductions $\endgroup$
    – vzn
    Dec 19 '13 at 17:39

I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.

Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P_2$ under polynomial-time Turing reductions.

Given a Boolean $(\wedge;\vee;\neg)$-formula $F$ and an integer $k$, is there an equivalent $(\wedge;\vee;\neg)$-formula of size at most $k$?

On p. 143, the authors state:

This provides a somewhat rare example of a natural problem for which a Turing reduction seems crucial (in the sense that we do not know of any simple modification or alternative methods that would give a many-one reduction).

They do not cite any other such examples from the literature. I suspect that "somewhat rare" is possibly an understatement.


David Buchfuhrer and Christopher Umans: "The complexity of Boolean formula minimization" Journal of Computer and System Sciences, Volume 77, Issue 1, January 2011, Pages 142-153


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.