A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [natural-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
18
votes
2answers
2k views

Hierarchy theorem for circuit size

I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area. Is it an interesting approach to class separation? The motivation for the question is that we ...
15
votes
2answers
924 views

Barriers and Monotone Circuit Complexity

Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit ...
15
votes
1answer
734 views

Random monotone function

In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the ...