<p>I think this situation is too general to draw many conclusions, but here goes...</p>

<p>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.</p>

<p>One way to paraphrase the original statement is: to make the classes equal in power requires more than a single query. </p>

<p>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.</p>

CC BY-SA 3.0
2011-11-01T01:47:52.473Z
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
CC BY-SA 3.0
2011-11-02T01:19:37.007Z
@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
CC BY-SA 3.0
2011-11-02T15:55:50.540Z
@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
CC BY-SA 3.0
2011-11-03T22:03:04.633Z
@Joshua I think we are confused... No restriction on number of queries you can have for Cook-like reduction...
Tayfun Pay
CC BY-SA 3.0
2011-11-04T16:03:12.633Z
@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
CC BY-SA 3.0
2011-10-31T15:17:00.730Z
2011-10-31T15:17:00.730Z
Joshua Grochow
<p>Assume we have two counting (functional) complexity classes $A$ and $B$. Suppose that</p>

<ol>
<li>Under Karp-like reductions $A$ is strictly inside $B$.   </li>
<li>Under Cook-like reductions $P^A=P^B$.</li>
</ol>

<blockquote>
  <p>What does this tell us about the relationship between these two
  counting complexity classes?</p>
</blockquote>

CC BY-SA 3.0
2011-10-28T03:01:06.063Z
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
CC BY-SA 3.0
2011-10-28T17:21:18.700Z
Some motivation might help
Suresh Venkat
<cc.complexity-theory><complexity-classes><counting-complexity>
Karp-like reductions vs Cook-like reductions for Functional Complexity Classes. 
Tayfun Pay
# Karp-like reductions vs Cook-like reductions for Functional Complexity Classes. 

(Asked by: username_0 on 2011-10-27)

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?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: I'm not sure I understand. Are you stating that A and B satisfy the given properties and then asking what this might mean ?  
> **username_1**: Some motivation might help  

---

## 1 answers

### Answer by username_2 on 2011-10-31. Score: 2 | Accepted 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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: @TayfunPay if you are restating your question, then you should edit the question itself instead of leaving restatements as comments on an answer.  
> **username_2**: @username_0: 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.  
> **username_0**: @Joshua I think we are confused... No restriction on number of queries you can have for Cook-like reduction...  
> **username_2**: @username_0: 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.  

---

