Lower Bounds for QBFs of Bounded Treewidth

DOI10.1145/3373718.3394756OpenAlexW3030023697MaRDI QIDQ5145651

Johannes K. Fichte, Andreas Pfandler, Markus Hecher

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.01047

zbMATH Keywords

treewidthlower boundspathwidthparameterized complexityquantified Boolean formulasETH

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Related Items (5)

Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ A practical account into counting Dung's extensions by dynamic programming ⋮ Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs

This page was built for publication: Lower Bounds for QBFs of Bounded Treewidth