Remix.run Logo
Ar-Curunir 2 hours ago

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.