New answers tagged ds.algorithms
0
This is an answer to the updated question (the original question seems harder).
Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses has a $O(2^{\mu'_k m})$ time algorithm.
Let $\mu_k$ be the smallest constant such that $k$-SAT with any clauses of length at most $k$ has an $O(2^{\mu_k m})$ time ...
1
See the intro of https://arxiv.org/abs/1912.08805 for a discussion of the literature around this problem. In short: O(n^3) has been known for symmetric matrices since the 60's, but was not known in general until recently.
Top 50 recent answers are included
