1 problem
- 0 votes0 replies0 views
Asymptotic gap between monotone and non-monotone formula complexity
Let and, for , let … Consider formula encodings whose gates are restricted to \{+,\times,\text{^}\} and whose inputs are restricted to . The asymptot…