On Tseitin formulas, read-once branching programs and treewidth.
Ludmila GlinskihDmitry ItsyksonPublished in: Electron. Colloquium Comput. Complex. (2019)
Keyphrases
- read once formulas
- boolean functions
- semidefinite
- tree decompositions
- bounded treewidth
- uniform distribution
- constraint satisfaction problems
- semidefinite programming
- upper bound
- propositional formulas
- search space
- max sat
- boolean formula
- membership queries
- interior point methods
- higher dimensional
- reduced error pruning
- convex relaxation
- sufficient conditions
- linear programming
- worst case
- np hard