Showing 2026Show all
3 papers · 1 filter
cs.CC2026
Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
Victor Lagerkvist, Johanna Groven, Leif Eriksson
The region connection calculus () and Allen's interval algebra () are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n…
cs.CC2026
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
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…
cs.DS2026
Backdoors for Quantified Boolean Formulas
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
The quantified Boolean formula problem (QBF) is a well-known PSpace-complete problem with rich expressive power, and is generally viewed as the SAT analogue for PSpace. Given that…