| ▲ | pcstl 8 hours ago | |
This proves that EXP != NP, which was a stronger claim than P != NP. In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen. It is definitely progress towards an answer to P ?= NP. | ||
| ▲ | jibalt 5 hours ago | parent | next [-] | |
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. | ||
| ▲ | 8 hours ago | parent | prev [-] | |
| [deleted] | ||