← Back to context Comment by pcstl 12 hours ago *Can be solvedThis proves that EXP != NP 6 comments pcstl Reply jibalt 9 hours ago 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 12 hours ago I'm stating the conjecture as requested pcstl 12 hours ago I think you misunderstood, I believe they were requesting a layperson-friendly explanation of the conjecture and not a statement of it. jibalt 9 hours ago 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 moishe_syzslak 11 hours ago Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue. caughtinthought 12 hours ago Which is a separate issue than the one you commented originally
jibalt 9 hours ago 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 12 hours ago I'm stating the conjecture as requested pcstl 12 hours ago I think you misunderstood, I believe they were requesting a layperson-friendly explanation of the conjecture and not a statement of it. jibalt 9 hours ago 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 moishe_syzslak 11 hours ago Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue. caughtinthought 12 hours ago Which is a separate issue than the one you commented originally
pcstl 12 hours ago I think you misunderstood, I believe they were requesting a layperson-friendly explanation of the conjecture and not a statement of it. jibalt 9 hours ago 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 moishe_syzslak 11 hours ago Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue. caughtinthought 12 hours ago Which is a separate issue than the one you commented originally
jibalt 9 hours ago 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
moishe_syzslak 11 hours ago Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue.
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.
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.
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
Whenever someone asks for an ELI5, there's always got to be somebody who further confuses the issue.
Which is a separate issue than the one you commented originally