Comment

Comment by krackers

[deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP.

And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]

parent krackers 5 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton