Encyclopedia > N > Natural proof
Natural proof
In computational complexity theory, a natural proof is a notion introduced by Alexander Razborov and Steven Rudich to describe a class of proofs for proving lower bounds on the circuit complexity of a boolean function. The proofs they describe show, either directly or indirectly, that a boolean function has a certain natural combinatorial property.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)