logoalt Hacker News

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

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."


Replies

adgjlsfhk1 • yesterday at 11:50 PM

OTOH, it would be surprising if this sort of technique didn't apply to other NP problems.

➕ show 1 reply