ECCC
Electronic Colloquium on Computational Complexity
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: Vinodchandran Variyam
Publication: 8th July 2004 19:16
Downloads: 1353
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