计数版 #PPM（Permutation Pattern Matching）询问在长度为 $n$ 的宿主排列中出现给定模式的次数。已有算法快于朴素 $O^*(2^n)$，当前最佳时间 $O(1.415^n)$（Gawrychowski 与 Rzepecki），且已知 PPM 在 ETH 下是硬的：若存在 $2^{o(n/\log n)}$ 的算法，则可得到 3SAT 的子指数算法（Jelínek 等）。本文给出相反方向的归约：若能在 $2^{O(n/f(n))}$ 时间内计数 3‑CNF 公式的满足赋值（#3SAT），其中 $n$ 为变量数，则可在 $2^{O\!\left(n\sqrt{\log f(n)}/f(n)\right)}$ 时间内求解 #PPM。特别地，OpenAI 最近声称推翻 ETH，暗示存在 $f(n)\in\Omega(\sqrt{\log n}/\log\log n)$ 的改进因子，从而通过我们的归约得到 #PPM 的子指数算法。
点评