<p>The <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qnc0" rel="nofollow noreferrer">Complexity Zoo</a> includes the class QNC<span class="math-container">$^0$</span>, which does not seem to be a class of decision problems. When I chase the references of the link provided, they say</p>

<blockquote>
  <p>“To extend this definition from quantum operators to decision problems in the classical sense, we have to choose a measurement protocol, and to what extent we want errors bounded. We will not explore those issues here.” </p>
</blockquote>

<p>(<a href="https://arxiv.org/abs/quant-ph/9804034" rel="nofollow noreferrer">https://arxiv.org/abs/quant-ph/9804034</a>)</p>

<p>I guess any attempt at making a decision problem version will lead to QNC<span class="math-container">$^0$</span> = NC<span class="math-container">$^0$</span> since the output of the circuits will only depend on a constant number of bits of the input.</p>

<p>On the other hand, the <a href="https://www.math.ucdavis.edu/~greg/zoology/intro.html" rel="nofollow noreferrer">zoology introduction</a> states</p>

<blockquote>
  <p>Some of the classes in the Zoo are not suitable for this Zoology project because they are not decision classes [...]</p>
</blockquote>

<p>Hence the question: Is the Complexity Zoo <a href="https://www.math.ucdavis.edu/~greg/zoology/diagram.xml" rel="nofollow noreferrer">Active Inclusion Diagram</a> supposed to be about classes of decision problems only?</p>

CC BY-SA 4.0
2019-11-04T23:05:33.597Z
Your reasoning sounds correct to me. If you restrict it to decision problems, then QNC^0 = NC^0.
Alessandro Cosentino
CC BY-SA 4.0
2019-11-05T07:03:34.807Z
@SankethMenda Thanks, now I've edited the question to be specifically about the Active Inclusion Diagram (which doesn't have Pcc I think)
Bjørn Kjos-Hanssen
<circuit-complexity><circuit-depth>
Is the Complexity Zoo Inclusion Diagram exclusively about classes of decision problems?
Bjørn Kjos-Hanssen
# Is the Complexity Zoo Inclusion Diagram exclusively about classes of decision problems?

(Asked by: username_0 on 2019-11-04)

The [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qnc0) includes the class QNC$^0$, which does not seem to be a class of decision problems. When I chase the references of the link provided, they say

> “To extend this definition from quantum operators to decision problems in the classical sense, we have to choose a measurement protocol, and to what extent we want errors bounded. We will not explore those issues here.”

(<https://arxiv.org/abs/quant-ph/9804034>)

I guess any attempt at making a decision problem version will lead to QNC$^0$ = NC$^0$ since the output of the circuits will only depend on a constant number of bits of the input.

On the other hand, the [zoology introduction](https://www.math.ucdavis.edu/~greg/zoology/intro.html) states

> Some of the classes in the Zoo are not suitable for this Zoology project because they are not decision classes [...]

Hence the question: Is the Complexity Zoo [Active Inclusion Diagram](https://www.math.ucdavis.edu/~greg/zoology/diagram.xml) supposed to be about classes of decision problems only?

**Tags:** circuit-complexity, circuit-depth
> **Comments:**
> **username_1**: Your reasoning sounds correct to me. If you restrict it to decision problems, then QNC^0 = NC^0.  
> **username_0**: @SankethMenda Thanks, now I've edited the question to be specifically about the Active Inclusion Diagram (which doesn't have Pcc I think)  

---

## 0 answers

