Hacker News

points by krackers 3 days ago | 0 comments

https://github.com/openai/math/tree/main/preprints/The-Expon...

>We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary k-CNF formula [in superpolynomial but subexponential time]

[–] baq 3 days ago

What a time to be alive honestly. Can’t know what one will wake up to

[–] mFixman 2 days ago

I assumed all new breakthroughs in advanced complexity theory would be theoretical and non-constructive, as in "we prove that this algorithm must exist but we do not provide it".

I'm genuinely shook at today's results, specially at the fact that there _is_ a constructive algorithm.

[–] adverbly 3 days ago

> superpolynomial

I've got some reading to do it seems...

[–] QuesnayJr 3 days ago

Polynomial is something like exp(n log x), where x is the problem size. Exponential is something like exp(x). Superpolynomial but subexponential is roughly when the exponent is between n log x and x. An exponent of (log x)^2 would do the trick.

The actual exponent OpenAI found was x/sqrt(x).

[–] pfdietz 2 days ago

x/sqrt(log(x)), I believe.