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?

1 Answer

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.