logoalt Hacker News

pcstl • yesterday at 11:19 PM • 2 replies • view on HN

*Can be solved

This proves that EXP != NP


Replies

jibalt • today at 2:24 AM

This is not a proof that NP != EXP. NP is poly time reduceable to 3SAT + 3SAT is sub-exponential does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.

Note https://news.ycombinator.com/item?id=50253213 which explains it better.

caughtinthought • yesterday at 11:21 PM

I'm stating the conjecture as requested

➕ show 1 reply