Local reduction

Jahanjou, H; Miles, E; Viola, E

Jahanjou, H (reprint author), Northeastern Univ, Boston, MA 02115 USA.

INFORMATION AND COMPUTATION, 2018; 261 (): 281

Abstract

We reduce non-deterministic time T >= 2(n) to a 3SAT instance phi quasilinear size | phi| = T center dot log(O(1)) Tsuch that there is an explicit ......

Full Text Link