Formula lower bounds via the quantum method
Avishay Tal · 2017
A de Morgan formula over Boolean variables x1,…,xn is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires a large formula is a central open question in computational complexity. While we believe that some explicit functions require exponential formula size, currently the best lower bound for an explicit function is the Ω(n3) lower bound for Andreev's function.