This is an amazing and unexpected result. To be clear though, it does not imply that NP is subexponential: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems
admit subexponential time algorithms."
Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.
If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.
But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.
Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
Edit: To explain more, it is guaranteed that you can reduce any NP problem to 3SAT in polynomial time with a polynomial factor in input size. You still have to solve it.
If 3SAT were solvable in polynomial time, then polynomial(polynomial(x)) = polynomial(x) and you're implied to have an overall polynomial time solution.
But what we have here is that 3SAT is solveable in subexponential time. subexponential(polynomial(x)) is not guaranteed to be sub-exponential.
Further edit: The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.