Under the auspices of the Computational Complexity Foundation (CCF)

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 ... more >>>

ISSN 1433-8092 | Imprint