ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > LOWER BOUNDS IN NON-UNIFORM COMPLEXITY:
Reports tagged with lower bounds in non-uniform complexity:
TR94-010 | 12th December 1994
Alexander Razborov, Steven Rudich

Natural Proofs

We introduce the notion of {\em natural} proof. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in non-monotone models fall within our definition of natural. We show based on a hardness assumption that natural proofs can't prove superpolynomial lower bounds for general ... more >>>



ISSN 1433-8092 | Imprint