logoalt Hacker News

gewetensleegte • today at 9:23 AM • 0 replies • view on HN

> 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.

No, subexponential is not the same as polynomial time. There's sub-exponential functions that grow faster than polynomial.