Local reductions

Abstract: We reduce non-deterministic time

T g e 2^{n}

to a 3SAT instance

p h i

of quasilinear size

| p h i | = T c d o t l o g^{O (1)} T

such that there is an explicit circuit

C

that on input an index

i

of

l o g | p h i |

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}

. Even in the simpler setting of polynomial size

| p h i | = p o l y (T)

the previous best result was

C

in AC

^{0}

. More generally, for any time

T g e n

and parameter

r l e q n

we obtain

l o g_{2} | p h i | = m a x (l o g T, n / r) + O (l o g n) + O (l o g l o g T)

and each output bit of

C

is a decision tree of depth

O (l o g r)

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

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Local reductions