Comment by caughtinthought | Hacker News Reader

Top New Best Ask Show Jobs

Comment by caughtinthought | Hacker News Reader

Parent Full thread

caughtinthought·

3SAT can't be solved in sub-exponential time

Fwiw never thought it was a well-named conjecture

*Can be solved

This proves that EXP != NP

I'm stating the conjecture as requested

I think you misunderstood, I believe they were requesting a layperson-friendly explanation of the conjecture and not a statement of it.

Which is a separate issue than the one you commented originally

Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue.

How is "This proves that EXP != NP", which is false, a layperson-friendly explanation of the actual proof that 3SAT is sub-exponential?

Note https://news.ycombinator.com/item?id=50253213

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.

Reply on news.ycombinator.com