Beating brute force for (quantified) satisfiability of circuits of bounded treewidth

MaRDI QIDQ4607895zbMATH OpenFDO

Authors Daniel Lokshtanov, Ivan Mikhailin, Ramamohan Paturi, Pavel Pudlák

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175284

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Counting truth assignments of formulas of bounded tree-width or clique-width
• On the satisfiability of quantum circuits of small treewidth
• Balancing Bounded Treewidth Circuits
• Width-parametrized SAT: time-space tradeoffs
• Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity

Cited in

(9)

• Size-treewidth tradeoffs for circuits computing the element distinctness function
• On treewidth, separators and Yao's garbling
• On the satisfiability of quantum circuits of small treewidth
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• A SAT-Based Approach for Index Calculus on Binary Elliptic Curves
• scientific article; zbMATH DE number 7238987 (Why is no real title available?)
• Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity
• Solving d-SAT via Backdoors to Small Treewidth
• Width-parametrized SAT: time-space tradeoffs

This page was built for publication: Beating brute force for (quantified) satisfiability of circuits of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607895)