Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds.

Olaf Beyersdorff Joshua Blinkhorn

Published in: Electron. Colloquium Comput. Complex. (2017)

Keyphrases

lower bound
upper bound
boolean formula
branch and bound algorithm
objective function
quantified boolean formulas
conjunctive normal form
max sat
lower and upper bounds
worst case
np hard
branch and bound
vc dimension
upper and lower bounds
mathematical formulas
equivalence queries
sample size