30
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ "Known to be NP-compete only under Cook reductions" or "only known to be NP-complete under Cook reductions"? $\endgroup$
    – David Richerby
    Commented Dec 17, 2013 at 21:05
  • 1
    $\begingroup$ NON-HAMILTONICITY. $\endgroup$
    – Yuval Filmus
    Commented Dec 19, 2013 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$
    – Yuval Filmus
    Commented Dec 19, 2013 at 16:06
  • 1
    $\begingroup$ See also this question: cstheory.stackexchange.com/questions/3333/…. $\endgroup$
    – Yuval Filmus
    Commented Dec 19, 2013 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
    Commented Dec 19, 2013 at 17:39

1 Answer 1

Reset to default
4
$\begingroup$

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.

References

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

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.