boolean_formula_lower_bound (1029B)
1 # Boolean formula lower bound 2 3 What are [lower_bounds] on the size of [Boolean_formulas] compared to [Boolean_circuits]? 4 5 [fischer1982omega]: the [modulo_3] [Boolean_function] has a size lower bound of Omega(n log n) over the [full_Boolean_basis] 6 7 [wegener1987complexity] Chapter 8 Theorem 5.2: the [Boolean_threshold_function] "at least two variables are true" on the basis [AND], [OR] and [NOT] needs size Omega(n log log n) 8 9 Better bounds are known for [positive_Boolean_formulas]: [wegener1987complexity] Chapter 8 Theorem 1.2 says that the threshold function needs size Omega(n log n) with [AND] and [OR] 10 11 [wegener1987complexity] Chapter 8 Theorem 8.2: the [parity_function] on the basis [AND], [OR] and [NOT] needs size Omega(n^2) 12 13 Best separation is in Omega(n^{3-o(1)}), cf [hastad1998shrinkage] and https://cstheory.stackexchange.com/questions/25555/may-boolean-circuits-be-exponentially-more-concise-than-boolean-formulae/25601 14 15 Related: https://cstheory.stackexchange.com/a/55791 16 17 Up: [lower_bound], [boolean_formula]