← Back to context Comment by caughtinthought 10 hours ago It basically just says that NP is not the same as EXP 1 comment caughtinthought Reply jibalt 7 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.
jibalt 7 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.
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.