The Complexity Zoo 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.”


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 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 supposed to be about classes of decision problems only?

  • 2
    $\begingroup$ Your reasoning sounds correct to me. If you restrict it to decision problems, then QNC^0 = NC^0. $\endgroup$ – Alessandro Cosentino Nov 4 at 23:05
  • 3
    $\begingroup$ The complexity zoo has all kinds of classes that complexity theorists care about; for example, Pcc is a communication complexity class. On a side note, just because two classes are equal does not imply that they are not interesting. IP=PSPACE but we still study them separately. $\endgroup$ – Sanketh Menda Nov 5 at 3:54
  • $\begingroup$ @SankethMenda Thanks, now I've edited the question to be specifically about the Active Inclusion Diagram (which doesn't have Pcc I think) $\endgroup$ – Bjørn Kjos-Hanssen Nov 5 at 7:03

Your Answer

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

Browse other questions tagged or ask your own question.