logoalt Hacker News

jibalt • today at 2:02 AM • 0 replies • view on HN

Your "No" is wrong. As he said, "Conversions to other problems can still end up exponential", so (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.