CS Paper Radar

Faster #PPM from faster #3SAT

László Kozma

cs.DS cs.CC ·submitted 2026-10-29 22:35 UTC · v1

Abstract

The counting variant (#PPM) of the permutation pattern matching (PPM) problem asks for the number of occurrences of a permutation pattern in a host permutation of length $n$. The problem admits faster algorithms than the trivial $O^*(2^n)$ time enumeration; the best known running time, for both PPM and #PPM, is $O(1.415^n)$ (Gawrychowski and Rzepecki). It is also known that PPM is ETH-hard: an algorithm with running time $2^{o(n/\log{n})}$ would imply a subexponential algorithm for 3SAT (Jelínek, Opler, and Pekárek). We give a reduction in the opposite direction, showing that an algorithm for counting satisfying assignments of a 3-CNF formula (#3SAT) in time $2^{O({n}/{f(n)})}$, where $n$ is the number of variables, yields an algorithm for #PPM with running time $2^{O({n \sqrt{\log{f(n)}/{f(n)}}})}$. In particular, the recently claimed refutation of ETH by OpenAI implies a #3SAT algorithm with an improvement factor $f(n) \in Ω(\sqrt{\log{n}}/\log\log{n})$ in the exponent; this yields, through our reduction, a subexponential algorithm for #PPM.

Closest papers

Nearest neighbours by meaning across the whole index.

Lowered crossover points of Anthropic's subexponential 3-SAT algorithm

cs.CC cs.DS ·2026-10-30 ·Ruhollah Majdoddin
theorycode/data similarity 0.67
Abstract · 56 pages. Scripts: https://github.com/Majdoddin/anthropic-3sat-crossover

The October 2026 refutations of the Exponential Time Hypothesis count satisfying assignments in time $2^{o(n)}$, but an asymptotic bound does not say from which input size, the crossover point, they beat the best known algorithms. We make the #3-SAT recursion of Anthropic's algorithm explicit and lower its crossover points, computed from the main term of the proved bound, by proved changes. For the bound in the number $m$ of clauses, at clause density one, the crossover point drops to about $2^{420}$ clauses from $2^{33858}$; for general 3-SAT, in the number $n$ of variables, our estimate drops to $2^{8.6\cdot10^9}$ variables from $2^{2.2\cdot10^{12}}$. With integer tables the recursion counts, for every $j$, the assignments satisfying exactly $j$ clauses in time $2^{O(m/\sqrt{\log m})}$. We observe that this refutes the Sparse Max-3-SAT Hypothesis of Alman and Vassilevska Williams, which also follows from either refutation by the reduction of Impagliazzo, Paturi and Zane, and we lower the crossover point of this computation to about $2^{1016}$ clauses from $2^{68364}$. The distance is structural: we define a rewrite-and-merge class that contains the recursion and all our constructions, and prove that in the main-term model no grid algorithm in it can gain for general 3-SAT below about $2^{6000}$ variables. For two balanced homogeneous merges we prove with quantum functionals an exponent of at least $(\log_2K)^{-3}$ per edge bit, which excludes running times $2^{n^{1-c}}$. Independently of SAT, we formalise the algorithm as a model of computation, Signed Network Sums, which contains rank-one methods and contraction trees. On the complete graph with four nodes, one-level constructions contract the network in $N^{23/6}$ if $ω=2$ and in about $N^{3.93}$ on the current (preprint) matrix-multiplication curve, below the bound $N^4$ of every rank-one method or contraction tree.

0.63

Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds

cs.DS ·2026-10-11 ·Sanjay Jain, Junqiang Peng, Frank Stephan, Mingyu Xiao
similarity 0.65
Abstract

Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{mω/3})$, where $ω< 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

0.29

Range Queries for Permutation Pattern Matching: Separations, Equivalences, and Applications

cs.DS ·2026-10-18 ·Omri Ben-Eliezer, Tomer Even
top venue similarity 0.64
Abstract · 48 pages. To appear in SODA 2027. Abstract shortened to meet arXiv requirements

The problem of Permutation Pattern Matching (PPM) asks, given a permutation $π:[n]\to[n]$, viewed as the point set $P=\{(i,π(i)):i\in[n]\}$, and a pattern $σ$ of small length $k$, whether $P$ contains an order-isomorphic copy of $σ$. The PPM problem and its (exact and approximate) counting variants have been studied extensively in the literature. We consider a preprocessing-query version: after preprocessing $P$, one must determine whether a query $P'\subseteq P$ contains $σ$, where $P'$ is obtained by intersecting $P$ with a geometric shape (e.g., an axis-aligned rectangle or $k$ such rectangles). This naturally generalizes the classical range query problem in computational geometry, which corresponds to the case $|σ|=1$. We extend the study of this problem from patterns of length $2$ to patterns of length $3$ (and in some cases beyond), and prove new fine-grained equivalences, separations, and applications: (1) Single rectangle: For all patterns of length $3$, detection can be done with $\tilde{O}(n)$ preprocessing and $\tilde{O}(1)$ query time. The proof goes through a new tool of independent interest: reductions from rectangle queries to a simpler family of slab queries. (2) Multiple rectangles: For $σ=132$, detection is equivalent to the online set disjointness problem; we also show connections to online $k$-set disjointness. To our knowledge, this is the first equivalence between a PPM-type problem and online set disjointness, a problem playing a fundamental role in fine-grained complexity. (3) Counting: As applications, we obtain an $O(n^{1.725})$ time algorithm for exact counting of $5$-patterns based on the rectangle-to-slab reduction, improving upon [Beniamini and Lavee, ICALP 2025], and an $\tilde{O}(n^{7/4})$ approximate counting algorithm for $6$-patterns, the first to break the $O(n^2)$ barrier for $6$-patterns.

0.46

Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF

cs.DS ·2026-11-06 ·Minbo Gao, Kun He, Tao Jiang
similarity 0.60
Abstract

We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.

0.33

Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231

cs.DM math.COcs.DScs.LO ·2026-09-14 ·Henning Arnór Skeggi Úlfarsson
code/data similarity 0.59
Abstract · 36 pages, 4 figures, 1 table. v2: revised and shortened exposition, corrected account of prior work, the first 151 terms tabulated, a proved…

We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance $3.5\cdot10^{-5}$ of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.

0.32

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.59
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27

Unranking $S$-avoiding permutations with two forbidden offsets

cs.DM math.CO ·2026-10-09 ·Antônio Augusto André
similarity 0.59
Abstract · 6 pages

Given a finite family of combinatorial objects with a total order, ranking asks for the position of a given object, and unranking asks for the object occupying a given position. Both provide algorithmic access to families too large to enumerate. Kagey gave a polynomial-time algorithm for several position-restricted families and left open the case of $\{-1,1\}$-avoiding permutations. We show that when $|S| = 2$, the graph of forbidden squares is $2$-regular, a disjoint union of cycles, and that fixing a prefix leaves only paths and untouched cycles. This yields polynomial-time prefix counting, ranking and unranking for every two-element set of offsets, covering $\{-1,1\}$. The same structure gives a short proof that the number of $\{-1,1\}$-avoiding permutations equals the $n$-th ménage number for odd $n$ and exceeds it by $2$ for even $n$, proving a conjecture recorded in the OEIS entry A354152.

0.20

Enumeration Complexity of Permutation Classes

cs.CC math.CO ·2026-10-27 ·Manuel Bodirsky, Mohamed Elsheikh
theory similarity 0.58
Abstract

We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $B$. However, our main notion of efficiency is polynomial delay. We use the insert-maximum tree as a search tree, in which permutations are built by repeatedly inserting a new maximum while preserving pattern avoidance. This leads to the \emph{insert-maximum extension problem}, which asks if a given permutation has an avoiding descendant at a specified depth. An algorithm for this problem can prune branches that cannot reach the target length. Hence, if this problem is in P, we obtain polynomial-delay enumeration. To investigate this problem, we introduce and study \emph{pockets}, the maximal finite subtrees of the insert-maximum tree. For fixed $B$, if there is a polynomial $p$ such that every pocket rooted at $ρ$ has at most $p(|ρ|)$ nodes, then the extension problem is solvable in polynomial time and enumeration has polynomial delay. In particular, a bound on pocket depth depending only on $B$ suffices. We prove such a bound if the class is well-quasi-ordered, has a regular insertion encoding, or if $B$ omits one of the three maximum-position types: leftmost, interior, or rightmost. We also prove that extension is in NP for every fixed $B$, even with binary-encoded target depth. On the negative side, we construct a fixed set of $55$ forbidden patterns for which extension is NP-complete. Consequently, enumerating valid extensions from a given starting permutation cannot have polynomial delay unless P=NP. This also answers a question of Hanika by showing that the forbidden permutation constraint satisfaction problem can be NP-complete for a fixed forbidden set.

0.08