1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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$
    – Suresh Venkat
    Oct 28, 2011 at 3:01
  • 5
    $\begingroup$ Some motivation might help $\endgroup$
    – Suresh Venkat
    Oct 28, 2011 at 17:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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, 2011 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$
    – Artem Kaznatcheev ♦
    Nov 2, 2011 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$
    – Joshua Grochow
    Nov 2, 2011 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, 2011 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$
    – Joshua Grochow
    Nov 4, 2011 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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