Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines.

Iannis Tourlakis

Published in: Computational Complexity Conference (2000)

Keyphrases

lower bound
upper bound
search space
max sat
boolean satisfiability
branch and bound algorithm
low dimensional
branch and bound
search algorithm
optimal solution
objective function
constraint satisfaction problems
worst case
phase transition
sat solvers
lower and upper bounds
data structure