AI RESEARCH
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
arXiv CS.AI
•
ArXi:2605.12073v1 Announce Type: cross Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to problems in NP, a lack of positive theoretical results, and in the parameterized complexity setting one often has to restrict the quantifier prefix (e.g., bounding alternations) to obtain fixed parameter tractability