logoalt Hacker News

wbl • yesterday at 11:30 PM • 5 replies • view on HN

No. NP is always poly time reduceable to 3SAT


Replies

cochne • yesterday at 11:38 PM

See this from the paper: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms."

➕ show 2 replies
mswphd • today at 12:35 AM

practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.

jibalt • today at 2:02 AM

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.

LPisGood • today at 2:39 AM

Subexponential(poly(n)) may be exponential in n

dataflow • yesterday at 11:56 PM

Did you reduce in the wrong direction or am I misunderstanding what you're trying to say?