logoalt Hacker News

xigoi • today at 8:58 AM • 0 replies • view on HN

Even if all NP problems could be solved in sub-exponential time, it would not imply that NP ≠ EXP. It seems that many people here are confused about what EXP means – it’s the set of all problems that can be solved in at most exponential time, including those in P.