Local Reductions

We reduce non-deterministic time

$$T \ge 2^n$$

T

≥

2

n

to a 3SAT instance

$$\phi $$

ϕ

of quasilinear size

$$|\phi | = T \cdot \log ^{O(1)} T$$

|

ϕ

|

=

T

·

log

O

(

1

)

T

such that there is an explicit circuit

C

that on input an index

i

of

$$\log |\phi |$$

log

|

ϕ

|

bits outputs the

i

th clause, and each output bit of

C

depends on

O

(1) input bits. The previous best result was

C

in NC

$$^1$$

1

. Even in the simpler setting of polynomial size

$$|\phi | = \mathrm {poly}(T)$$

|

ϕ

|

=

poly

(

T

)

the previous best result was

C

in AC

$$^0$$

0

.

More generally, for any time

$$T \ge n$$

T

≥

n

and parameter

$$r \le n$$

r

≤

n

we obtain

$$\log _2 |\phi | = \max (\log T, n/r) + O(\log n) + O(\log \log T)$$

log

2

|

ϕ

|

=

max

(

log

T

,

n

/

r

)

+

O

(

log

n

)

+

O

(

log

log

T

)

and each output bit of

C

is a decision tree of depth

$$O(\log r)$$

O

(

log

r

)

.

As an application, we tighten Williams’ connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).