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?

  • 2
    $\begingroup$ I'm not sure I understand. Are you stating that A and B satisfy the given properties and then asking what this might mean ? $\endgroup$ Oct 28 '11 at 3:01
  • 5
    $\begingroup$ Some motivation might help $\endgroup$ Oct 28 '11 at 17:21

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.

  • $\begingroup$ 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? $\endgroup$
    – Tayfun Pay
    Nov 1 '11 at 1:47
  • $\begingroup$ @TayfunPay if you are restating your question, then you should edit the question itself instead of leaving restatements as comments on an answer. $\endgroup$ Nov 2 '11 at 1:19
  • $\begingroup$ @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. $\endgroup$ Nov 2 '11 at 15:55
  • $\begingroup$ @Joshua I think we are confused... No restriction on number of queries you can have for Cook-like reduction... $\endgroup$
    – Tayfun Pay
    Nov 3 '11 at 22:03
  • $\begingroup$ @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. $\endgroup$ Nov 4 '11 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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