arXiv preprint ·
Faster #PPM from faster #3SAT
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quantum Query Complexity of Tournament Solutions
Quantum query complexity of Hurwitz stability testing
Retrieval Sequencing in a Compact Storage System with Side Access
Lowered crossover points of Anthropic's subexponential 3-SAT algorithm
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.