Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-056 | 1st July 2004 00:00

A note on the circuit complexity of PP

RSS-Feed




TR04-056
Authors: N. V. Vinodchandran
Publication: 8th July 2004 19:16
Downloads: 5139
Keywords: 


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 $n^k$.



ISSN 1433-8092 | Imprint