logoalt Hacker News

Ar-Curuniryesterday at 6:22 PM0 repliesview on HN

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.