Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.