logoalt Hacker News

cochne • yesterday at 11:26 PM • 2 replies • view on HN

It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.


Replies

wbl • yesterday at 11:30 PM

No. NP is always poly time reduceable to 3SAT

➕ show 5 replies