logoalt Hacker News

imadr • yesterday at 11:56 PM • 2 replies • view on HN

P=NP -> 3SAT has a polynomial time algorithm

P=/=NP -> 3SAT has no polynomial-time algorithm

ETH is true -> 3SAT has no subexponential time algorithm

ETH is false -> 3SAT has a subexponential time algorithm

------

ETH true -> P=/=NP

ETH false (!!!) -> P ?= NP remain unsolved


Replies

demibabs • today at 12:01 AM

No I get that, but I don't get how proving 3SAT can be proved in subexponential time does not imply all NP-complete problems can be as well, since they can all be reduced to 3SAT in polynomial time.

➕ show 5 replies