New Lower Bounds Through an Improved Easy Witness Lemma
summary
Combines a strengthened easy witness lemma with the usual SAT-to-lower-bound framework to push from NEXP-style results down to NP: proving that a nontrivial SAT algorithm for 2^{ε n}-size circuits (roughly running in 2^{n−n^{ε}} time) yields that NP lacks fixed polynomial-size circuits (no n^k-size circuits for any fixed k). The new lemma shows that assuming NP has n^k-size circuits gives n^{k^3} witness circuits, letting witness guessing shrink and verification use the faster SAT algorithm to produce the contradiction.
AI-written summary · about