Article ID Journal Published Year Pages File Type
9657718 Theoretical Computer Science 2005 4 Pages PDF
Abstract
In this short note, we show that for any integer k, there are languages in the complexity class PP that do not have Boolean circuits of size nk.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A note on the circuit complexity of PP
Authors
,