alt Hacker Newshttps://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]
Replies
baq • yesterday at 10:46 PM
What a time to be alive honestly. Can’t know what one will wake up to
adverbly • yesterday at 11:19 PM
> superpolynomial
I've got some reading to do it seems...
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.