Remix.run Logo
▲ eru 8 hours ago

> Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time).

It's a bit more complicated than that, if you want to be careful. Sorting is in both NP and EXP and can be solved in subexponential time.

I think what they proved is that no problem in NP takes exponential time to solve. (Because you can always reduce them to SAT in polynomial time, and then solve SAT in subexponential time.)

EDIT: apparently the runtime bounds they gave here don't survive the usual polynomial reductions, thus they haven't proven that NP != EXP, it seems.

▲ 8 hours ago | parent [-]
[deleted]