Local reduction

We reduce non-deterministic time T ≥ 2 n to a 3SAT instance ϕ of quasilinear size | ϕ | = T ⋅ log O ( 1 ) ⁡ T such that there is an explicit NC 0 circuit C that encodes ϕ in the following way: on input a ( log ⁡ | ϕ | ) -bit index i, C outputs the ith clause of ϕ. The previous best result was C in NC1. Even in the simpler setting of polynomial size ( | ϕ | = poly ( T ) ), the previous best result was C in AC0. More generally, for any time T ≥ n and parameter r ≤ n we obtain | ϕ | = max ⁡ ( T, 2 n / r ) ⋅ ( n log ⁡ T ) O ( 1 ), and each output bit of C is a decision tree of depth O ( log ⁡ r ). As an application, we tighten Williams' connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).

Authors

• Hamidreza Jahanjou
• Eric Miles
• Emanuele Viola

Keywords

• Computational complexity
• Cook–Levin
• Reductions
• ACC0