# SAT and Polytime Reductions

If an algorithm for $$SAT$$ runs in $$O(n^{\log n})$$ time, and if $$L$$ belongs to $$\mathsf{NP}$$, is there an algorithm for $$L$$ that runs in $$O(n^{\log n})$$ time?

## 2 Answers

As $$\mathrm{SAT}$$ is $$\mathrm{NP}$$-complete, we know that there is a polytime reduction from our language $$L$$ to $$\mathrm{SAT}$$. However, this reduction can involve a polynomial blowup of the input size. This means that an input $$w$$ to $$L$$ could be mapped to a formula $$\phi_w$$ such that $$|\phi_w| \approx |w|^k$$ for some constant $$k$$.

Running our hypothetical algorithm for $$\mathrm{SAT}$$ on $$\phi_w$$ takes time $$O(|\phi_w|^{\log |\phi_w|}) = O((|w|^k)^{\log |w|^k}) = O(|w|^{k^2 \log |w|})$$ time. But $$O(n^{k^2 \log n}) \neq O(n^{\log n})$$.

Thus, there is no immediate reason why the assumption would yield an $$O(n^{\log n})$$-algorithm for $$L$$.

Since any input x for L can be reduced to SAT in O(|x|^c) time, the created SAT instance will have size at most n=O(|x|^c). So the n^(lg n)-time algorithm for SAT will be an |x|^O(lg |x|)-time algorithm for L.