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
  • 2
    $\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.