factual
No known superlinear lower bound for satisfiability
Moitra states that although SAT is believed to require exponential time, researchers know no lower bound on satisfiability that is asymptotically more than the time needed to read the input, which he calls a striking gap in understanding.
factualpending
Speaker
Ankur MoitraEvidence Quote
“we don't know anything that sort of is asymptotically more running time than just reading the darn input.”
Created: 11/17/2026, 6:25:32 AM
Your notes
Loading notes...