Local reductions

Original · EN

We reduce non-deterministic time T ≥ 2ⁿ to a 3SAT instance ϕ of quasilinear size |ϕ| = T · ᵒ⁽¹⁾ T such that there is an explicit circuit C that on input an index i of |ϕ| bits outputs the ith clause, and each output bit of C depends on O(1) input bits. The previous best result was C in NC¹. Even in the simpler setting of polynomial size |ϕ| = (T) the previous best result was C in AC⁰. More generally, for any time T ≥ n and parameter r ≤ n we obtain ₂ |ϕ| = (T, n/r) + O(n) + O(T) and each output bit of C is a decision tree of depth O(r). As an application, we tighten Williams' connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).