The counting version #PPM (Permutation Pattern Matching) asks for the number of occurrences of a pattern in a host permutation of length $n$. Algorithms faster than the trivial $O^*(2^n)$ are known; the current best running time is $O(1.415^n)$ (Gawrychowski and Rzepecki). It is also known that PPM is ETH‑hard: a $2^{o(n/\log n)}$ algorithm would yield a subexponential algorithm for 3SAT (Jelínek et al.). This work provides a reduction in the opposite direction: if #3SAT can be solved in $2^{O(n/f(n))}$ time, where $n$ is the number of variables, then #PPM can be solved in $2^{O\!\left(n\sqrt{\log f(n)}/f(n)\right)}$ time. In particular, the recent claim by OpenAI that refutes ETH implies an improvement factor $f(n)\in\Omega(\sqrt{\log n}/\log\log n)$, which through our reduction yields a subexponential algorithm for #PPM.
Review