← Back to context Comment by caughtinthought 12 hours ago 3SAT can't be solved in sub-exponential timeFwiw never thought it was a well-named conjecture 7 comments caughtinthought Reply pcstl 12 hours ago *Can be solvedThis proves that EXP != NP 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. 3 replies →
pcstl 12 hours ago *Can be solvedThis proves that EXP != NP 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. 3 replies →
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. 3 replies →
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. 3 replies →
*Can be solved
This proves that EXP != NP
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.
3 replies →