3 ms·

> That probably means no worse than O(N^2),... We don't even have a quadratic-time algorithm for matrix multiplication (and it's obvious that O(N^2) is a lower

> That probably means no worse than O(N^2),... We don't even have a quadratic-time algorithm for matrix multiplication (and it's obvious that O(N^2) is a lower bound).

tgflynn 11y ago
Nor do we have any proof of a lower bound > O( N ) for 3-SAT.