Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
5  
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
add comment

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.

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

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.