1
$\begingroup$

I just read about polynomial-size circuit families and I have a question as the title. I know P/poly is defined as the class PSIZE of languages that have polynomial-size circuits. But what about other languages in other classes that have polynomial circuits?

$\endgroup$
4
$\begingroup$

Some languages in P/poly are undecidable. For example, any language over the alphabet {a} is in P/poly because for any string length n, either an is in the language or it is not, so the advice string for length n can just be whether or not to accept the string. However, there are uncountably many languages over this alphabet and only countably many Turing machines, so infinitely many of these languages are undecidable.

Every language in PSPACE is, by definition, decidable. Therefore, PSPACE ≠ P/poly.

Hope this helps!

$\endgroup$

Your Answer

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