# Karp-like reductions vs Cook-like reductions for Functional Complexity Classes.

Assume we have two counting (functional) complexity classes $A$ and $B$. Suppose that

1. Under Karp-like reductions $A$ is strictly inside $B$.
2. Under Cook-like reductions $P^A=P^B$.

What does this tell us about the relationship between these two counting complexity classes?

-
I'm not sure I understand. Are you stating that A and B satisfy the given properties and then asking what this might mean ? –  Suresh Venkat Oct 28 '11 at 3:01
@suresh exactly! –  Tayfun Pay Oct 28 '11 at 12:27
Some motivation might help –  Suresh Venkat Oct 28 '11 at 17:21
So if A is Karp reducible to B then A is Turing reducible to B. If A is not Karp reducible to B, then it doesn't necessarily hold that A is not Turing reducible to B. –  Tayfun Pay Nov 25 '11 at 3:05

I think this situation is too general to draw many conclusions, but here goes...

If $A$ is closed under Cook-like reductions, then (2) would imply $B \subseteq A$, contradicting (1), so it tells you that $A$ is not closed under Cook-like reductions.

One way to paraphrase the original statement is: to make the classes equal in power requires more than a single query.

One can then ask about other intermediate types of reductions to get a better sense of just how many queries are needed and in what way e.g. are the classes equivalent under truth-table (nonadaptive) reductions? What's the best bound we can put on the number of queries ($2$, $O(1)$, $O(\log n)$?) Since these are counting classes, one could also ask about parsimonious reductions.

-
I am not restricting the number of queries you can have! –  Tayfun Pay Oct 31 '11 at 20:27
Let me rephrase it. We know that A is strictly inside B, then is it possible for them to be equivalent under Cook-Like Reductions where we allow as many queries as possible? –  Tayfun Pay Nov 1 '11 at 1:47
@TayfunPay if you are restating your question, then you should edit the question itself instead of leaving restatements as comments on an answer. –  Artem Kaznatcheev Nov 2 '11 at 1:19
@Tayfun Pay: If I understand correctly what you mean by "Karp-like" then Karp-like reductions necessarily only use a single query - it's built in to the definition. Otherwise, please give a more precise definition of what you mean by "Karp-like" reduction. –  Joshua Grochow Nov 2 '11 at 15:55
@Joshua I think we are confused... No restriction on number of queries you can have for Cook-like reduction... –  Tayfun Pay Nov 3 '11 at 22:03