CS Paper Radar

Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students

Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan

cs.CC cs.CY ·submitted 2026-08-13 08:56 UTC · v1
theory

Abstract

This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.

Comment
22 pages; 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Min-CSPs on Complete Instances III: Nearly Optimal Characterizations of Approximation for Symmetric CSPs

cs.DS ·2026-11-10 ·Yihwan Chae, Chenglin Fan, Donghyeon Lee, Euiwoong Lee
similarity 0.62
Abstract · 45 pages. Adjusted the placement of Table 1

This paper studies complete Min-$k$-CSPs: an instance on $n$ variables has one nontrivial constraint for every $k$-set of variables (so $\binom{n}{k}$ constraints in total), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. They are motivated by the connections to machine learning and data science, as well as the possibility of being testbeds for new algorithmic techniques. Previous recent results presented polynomial-time algorithms for the decision version of every complete Boolean $k$-CSP, which is a necessary condition for any multiplicative approximations for the minimization version, but nontrivial approximation results have been limited to fragile CSPs, 2-SAT, and NAE-3-SAT, leaving the approximability of most complete Boolean Min-CSPs open, including complete Min-$k$-SAT. In this paper, we resolve this question, up to nearly matching factors, for the natural class of symmetric Boolean predicates. Given $A \subseteq \{0, \dots, k\}$, Min-CSP($A$) is a Min-$k$-CSP where each constraint is specified by $k$ literals and is satisfied if the number of true literals belongs to $A$. Let $w(A)$ be the maximum number of consecutive integers in $A$. Our main results for complete Min-CSP($A$) are (1) a QPTAS for $w(A) \leq 2$ and (2) an $\widetilde{O}(n^{w(A)-3})$-approximation for $w(A) \geq 3$, as well as almost matching hardness results for the latter. Our QPTAS for $w(A)=2$ significantly improves the previous $O(1)$-approximation for Min-2-SAT and the $\operatorname{polylog}(n)$-approximation for Min-NAE-3-SAT, as well as extends the PTAS for fragile CSPs (i.e., $w(A) = 1$).

0.23

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.62
Abstract

Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

0.22

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity

cs.DS cs.CC ·2026-10-13 ·Jan Dreier, Robert Ganian, Marlene Gründel, Roohani Sharma, Simon Wietheger
similarity 0.60
Abstract

The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search and reasoning tasks. While $\mathrm{NP}$-complete in general, SAT is well known to be linear-time solvable on instances with bounded treewidth. This motivates the search for "hidden" tree-like structures in formulas---for instance by detecting so-called weak $t$-treewidth backdoors. Such backdoors are sets of $k$ variables that can be assigned in such a way that the remaining instance has treewidth at most $t$ and is satisfiable whenever the original instance is. Ever since Gaspers and Szeider [ICALP 2012] showed that finding a weak $t$-treewidth backdoor for a SAT formula is $\mathrm{W}[2]$-hard with respect to $k$, tractability results have been restricted to structurally sparse formulas---most notably, a linear-time algorithm for $d$-SAT (bounded clause-length SAT) by Fomin, Lokshtanov, Misra, Ramanujan, and Saurabh [SODA 2015] and a non-uniform polynomial-time algorithm when the incidence graph of the input formula belongs to a nowhere-dense graph class (or more generally is $K_{d,d}$-free) by Lokshtanov, Panolan, and Ramanujan [ICALP 2022]. In this paper, we push the tractability boundaries of finding weak $t$-treewidth backdoors beyond sparsity and into the regime of "well-behaved" dense formulas. Aiming towards relaxing structural input restrictions from nowhere-dense to edge-stable graph classes, as featured in the theory of beyond sparsity for FO model checking, or to bounded VC-dimension set systems, we identify signed semi-ladder-freeness as the correct dense structural restriction that establishes the boundary between tractability and intractability along this line.

0.48

Abelian embeddings make useful promises: approximation of detrivialised equations

cs.CC cs.DMcs.DS ·2026-11-03 ·Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný
theory similarity 0.60
Abstract

We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the variables that makes no equation monochromatic. For $p\in\{2,3\}$, the problem recovers known tractable Promise Constraint Satisfaction Problems (PCSPs). For $p > 3$, we obtain a complete complexity classification: the problem is polynomial-time solvable for $c \geq 4$, yet even its decision version is NP-hard for $c = 3$, and it is not well-defined for $c = 2$. Our main conceptual contribution is a general tractability framework for PCSPs based on Abelian embeddings, a notion introduced by Bhangale, Khot, and Minzer [STOC 2022] in the study of quantitative approximation of satisfiable CSPs. We show that suitable Abelian embeddings yield polynomial-time PCSP reductions realised by singleton algorithms in the sense of Zhuk [FOCS 2026]. On the hardness side, the promise relation is far removed from the reconfigurable regime covered by the conditional hardness framework of Banakh, Barsukov, and Nakajima [LICS 2026]; our proof instead relies on a new additive-combinatorial rigidity theorem classifying special $3$-colourings of $\mathbb{Z}_p$.

0.29

Cores Characterize the One-Pass Streaming Complexity of CSPs

cs.CC cs.DMcs.DS ·2026-10-05 ·Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy
similarity 0.59
Abstract

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly computing the maximum number of satisfied constraints. Sharma and Velusamy (ESA 2026) characterized the streaming complexity of satisfiability for CSPs with literals using the non-redundancy parameter $\textsf{NRD}_n(R)$, which roughly measures the largest instance in which every constraint is independently necessary. For the most general setting without literals, they obtained the corresponding characterization for Boolean relations and showed obstacles to extending their techniques to larger domains. Kol, Paramonov, Saxena, and Yu (ITCS 2023) similarly characterized the streaming complexity of $\textsf{Exact-CSP}(R)$ for Boolean CSPs with literals in terms of the degree deg$(R)$ of the relation when written as a polynomial, while without literals, the corresponding result was known only for $\textsf{Max-Cut}$. For all three of the objectives we study, we give tight characterizations for unweighted CSP instances over arbitrary finite domains. The streaming algorithms we provide are deterministic, while the corresponding bounds are tight up to polylogarithmic factors, even against randomized algorithms. The central idea in all three results is a reduction of $R$ to its core, a canonical subrelation of $R$ which admits gadgets that allow for the hard-pinning (or fixing) of variables.

0.15

The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning

cs.DS cs.CCcs.CY ·2026-10-02 ·Sherzod Turaev, Mary John, Mamoun Awad
theory similarity 0.59
Abstract · 17 pages, 2 figures, 2 tables

We model an academic curriculum as a generator of a language of feasible study plans: prerequisites are monotone Boolean formulas in conjunctive normal form, degree requirements are credit-threshold covering constraints, and a study plan is a sequence of terms bounded by a per-term credit capacity. Within this model, we settle the complexity of the two natural planning objectives, the number of terms to a degree and the total credit load, and we isolate the structural commitment responsible for each source of hardness. Time to degree is polynomial whenever the per-term capacity is unbounded, for arbitrary disjunctive prerequisites and arbitrary electives, so disjunction never contributes to its hardness, yet it becomes strongly NP-hard as soon as capacity binds, even without any prerequisite. Load is complementary: disjunction and overlapping electives are each strongly NP-hard in isolation and their complexity does not depend on capacity, while load is polynomial on the conjunctive, mandatory fragment. The two objectives therefore have disjoint sources of hardness. We show that the delay-factor component of the standard curricular-complexity metric is a polynomially computable upper bound on time to degree, exact on the conjunctive fragment and loose elsewhere by a quantity we name the disjunctive slack, and we prove that program subsumption is coNP-complete and consensus prerequisite recovery is NP-complete. Instantiating the model on a corpus of twenty-two universities, we find that 88 percent of prerequisite-bearing courses are purely conjunctive and that capacity, not prerequisite logic, is the operative constraint on time to degree. The curriculum corpus is openly available (https://doi.org/10.5281/zenodo.22334674), and the analysis and figure-generation code accompany the paper.

0.37

The Complexity of Computing Class Probabilities in BID Probabilistic Databases

cs.DS ·2026-09-18 ·Sotiris Kanellopoulos, Ioannis Koutras, Aris Pagourtzis
theory similarity 0.58
Abstract

We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database realizes each feasible tuple type, the goal is to compute the probability of a class of worlds specified by a given tuple multiplicity vector, thus grouping together worlds with the same bag (multiset) of realized tuple types. For this problem, we prove $\#\mathsf{P}$-hardness even for very restricted and structured inputs. On the other hand, we show that it admits an FPRAS, as well as $\mathsf{XP}$-time algorithms parameterized by the number of tuple types and the treewidth of an incidence graph modeling the connections between blocks and tuples. Finally, we show that augmenting the problem with certain compatibility constraints between block realizations renders it $\#\mathsf{XLP}$- and $\#\mathsf{XALP}$-hard parameterized by pathwidth and treewidth respectively, ruling out $\mathsf{FPT}$ algorithms under standard assumptions. We leave as an open question whether this also holds in the absence of compatibility constraints.

0.32

Robust Approximation and the Arity Barrier at Width Two

cs.CC ·2026-09-29 ·Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli
theory similarity 0.58
Abstract

Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint languages, Barto and Kozik proved that robust approximability is characterized by bounded width. We ask whether arity-independent robustness persists beyond width one and show that it fails already at width two. For Majority-closed Boolean linear constraints of maximum arity $k \ge 2$, we give a randomized polynomial-time algorithm that, without knowing $\varepsilon$, violates an expected $O(\sqrt{\varepsilon \log k})$ fraction of the constraint weight on $(1-\varepsilon)$-satisfiable instances. Under the Unique Games Conjecture (UGC), a matching NP-hardness lower bound of $Ω(\sqrt{\varepsilon \log k})$ holds in an explicit parameter regime. Under this assumption, the bounded-width characterization therefore does not extend uniformly to constraints of unbounded arity. The algorithm rounds a degree-eight Sum-of-Squares (SoS) relaxation with a single Gaussian threshold. Since polynomial size alone does not make SoS solvable in polynomial bit complexity, we construct complete truncated Groebner bases for the soft Majority ideal and show that, at every fixed degree $2d$, the relaxation can be optimized to any rational accuracy in polynomial time with exactly feasible solutions, and degree-$2d$ SoS proofs can be found after an additive perturbation at degree at most $4d+10$. The lower bound combines Raghavendra's gap-to-hardness theorem with an integrality gap on a Gaussian star, analyzed via the Isaksson-Mossel theorem that parallel halfspaces maximize the joint membership probability of exchangeable Gaussians.

0.44