While we today have quite powerful tools for solving problems that are NP-hard, or even harder ones, it is typically easy to give conditions where they exhibit impractical slow performance. When designing new, better, algorithms for these cases, understanding theoretical limits becomes crucial to avoid investing time in approaches that are ultimately dead ends. Modern conjectures, such as the exponential time hypothesis (ETH), enable us to establish effective theoretical lower bounds for many problems. These lower bounds often align closely with our best-known upper bounds, especially in problems over finite domains. However, this alignment tends to break down in cases involving infinite domains, or input-dependent domains, and for problems beyond NP. While we for some easier and harder infinite-domain problems have matching upper and lower bounds, there exists a wide range of problems where a significant knowledge gap remains. We specifically examine Allen’s interval algebra (Allen) and partially ordered time (POT), where the best known lower bounds are 2o(n). Both these problems can be formulated as infinite-domain constraint satisfaction problems (CSP) and exhibit this gap between upper and lower bounds. While these problems are solvable in 2O(n2) time by exhaustive search, we improve upon this and ultimately reach the first o(n)n algorithm for Allen. This result is the usage of dynamic programming, with a particular emphasis on tracking unsolved subproblems, rather than the more traditional approach of building upon already-solved subproblems.While a significant improvement over exhaustive search, to get closer to single-exponential running times of 2O(n2), we shift our focus to (multivariate) parameterized complexity. We begin by introducing two new single-exponential complexity classes: fixed parameter single-exponential (FPE) and slicewise single-exponential (XE), analogous to the well-known classes of fixed-parameter tractable (FPT) and slicewise polynomial (XP), respectively. We then apply these concepts to Allen and POT, showing both FPE and XE results.
In the latter part of the thesis we shift focus to a problem where further unconditional improvements are unlikely under the strong ETH: evaluating quantified Boolean formulas (QBF). Although this problem is the PSpace-complete analogue of the Boolean Satisfiability problem (SAT), it is comparatively understudied, and few positive algorithmic results are known. Focusing on how simplifying away a small set of variables (a backdoor) results in a tractable formula, we start by showing how removing all existential variables yields new FPT results. Building upon this, we then show multiple other backdoor results for classical tractable classes like 2-CNF, AFF and HORN, including both new hardness results and new FPT algorithms.
