Lower Bounds on the Size of Boolean Formulas: Preliminary Report

Michael J. Fischer Albert R. Meyer Mike Paterson

Published in: STOC (1975)

Keyphrases

lower bound
boolean formula
upper bound
optimal solution
branch and bound
branch and bound algorithm
objective function
computational complexity
max sat
equivalence queries
machine learning
genetic algorithm
worst case
heuristic search
sat solvers
vc dimension