Comment

Comment by luc4

I mean the result that k-SAT cannot be solved in 2^{o(n)} clearly would imply P!=NP, but how does ETH imply NP = EXP? And how does \neg ETH imply NP != EXP?
parent luc4 5 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton