4 ms·

Circuit complexity lower bounds (and lower bounds in general) are notoriously difficult to come across. For example, despite our best efforts, the state of the

Circuit complexity lower bounds (and lower bounds in general) are notoriously difficult to come across. For example, despite our best efforts, the state of the art lower bounds on time complexity of algorithms for solving 3SAT is O(n). In contrast, our best algorithms for the task run in time roughly O(2^n). That’s an exponential gap. This is despite decades of trying to find lower bounds.

ninkendo 2mo ago
> the state of the art lower bounds on time complexity of algorithms for solving 3SAT is O(n) Wow, that’s pretty stark. “What’s the minimum time it would take to solve this problem?” “Well, at the very least you’d have to read the input the whole way through”