logoalt Hacker News

tfpgh • today at 12:32 AM • 2 replies • view on HN

This isn't quite true, problems in NP can still require exponential time to solve.

Solving an arbitrary NP problem looks like first reducing that problem to SAT and then solving the equivalent SAT problem. We know (via the Cook–Levin theorem) that any NP problem can be reduced to SAT in polynomial time, and we now know that solving SAT is subexponential in terms of the size of the SAT problem, but it's possible for the conversion to SAT to grow the problem enough that it's exponential in terms of the original problem.


Replies

dnautics • today at 12:39 AM

thanks for the correction. Corrected.