# 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
• Some motivation might help – Suresh Venkat Oct 28 '11 at 17:21

## 1 Answer

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.

• 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
• @Tayfun Pay: Hopefully to help clarify: Karp-like has one query, Cook-like has as many as it wants (subject of course to the time restriction). This was the whole point of my answer: with only a single query, as in Karp-like reduction, $B$ is not contained in $A$, but when we close the classes under Cook-like (i.e. unlimited query) reductions, they become equal. – Joshua Grochow Nov 4 '11 at 16:03