▲
Hacker News
new
|
best
|
ask
|
show
|
jobs
points by
caughtinthought
3 days ago | 0 comments
It basically just says that NP is not the same as EXP
[–]
jibalt
3 days 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.
Hacker News
Note https://news.ycombinator.com/item?id=50253213 which explains it better.