# Graph problem known to be NPNP-complete only under Cook reduction

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.

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 $$ΣP2\Sigma^P_2$$ under polynomial-time Turing reductions.

Given a Boolean $$(∧;∨;¬)(\wedge;\vee;\neg)$$-formula $$FF$$ and
an integer $$kk$$, is there an equivalent $$(∧;∨;¬)(\wedge;\vee;\neg)$$-formula of size at most $$kk$$?

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