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$ – David Richerby Dec 17 '13 at 21:05
  • 1
    $\begingroup$ NON-HAMILTONICITY. $\endgroup$ – Yuval Filmus Dec 19 '13 at 5:38
  • 1
    $\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$ – Yuval Filmus Dec 19 '13 at 16:06
  • 1
    $\begingroup$ See also this question: cstheory.stackexchange.com/questions/3333/…. $\endgroup$ – Yuval Filmus Dec 19 '13 at 16:38
  • 2
    $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.