Comment

Comment by Aunche

Suppose 3sat is solved in 2^sqrt(n). That's subexponential. An n^2 reduction from sat to 3sat is polynomial. However, an algorithm using this reduction with the discovered solution, would run in (2^sqrt(n))^2 which is just 2^n.
parent Aunche 5 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton