Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMBINATORIAL PROPERTIES:
Reports tagged with combinatorial properties:
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 ... more >>>




ISSN 1433-8092 | Imprint