6
$\begingroup$

(This is a somewhat fuzzy question.)

I believe that most of the "standard" complexity classes that one comes across in complexity theory are countably infinite, because they are defined in terms of decision problems that can be solved by Turing machines with certain prescribed capabilities, and the set of Turing machines (on a given alphabet, etc.) is countable.

But certain complexity classes, like ALL, are uncountably infinite. Are any other "practically important" classes that come up on complexity theory uncountably infinite? What about in computability theory?

$\endgroup$

1 Answer 1

7
$\begingroup$

Nonuniform complexity class P/poly is uncountable. We can just choose for each input length its own circuit, so for any subset $S \subset \mathbb{N}$ the language $L_S = \{w \colon |w| \in S \}$ is in P/poly.

In general, nonuniform/advice complexity classes are usually uncountable for the same reason.

$\endgroup$

Your Answer

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

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