caa a22 4500 467909679 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20061201xx s 000 0 eng 10.1007/s00037-007-0221-1 doi (NATIONALLICENCE)springer-10.1007/s00037-007-0221-1 Williams Ryan Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut Inductive Time-Space Lower Bounds for Sat and Related Problems [Elektronische Daten] [Ryan Williams] Abstract.: We improve upon indirect diagonalization arguments for lower bounds on explicit problems within the polynomial hierarchy. Our contributions are summarized as follows. 1. We present a technique that uniformly improves upon most known nonlinear time lower bounds for nondeterminism and alternating computation, on both subpolynomial (n o(1)) space RAMs and sequential one-tape machines with random access to the input. We obtain improved lower bounds for Boolean satisfiability (SAT), as well as all NP-complete problems that have efficient reductions from SAT, and ∑ k -SAT, for constant k ≥ 2. For example, SAT cannot be solved by random access machines using $$n^{\sqrt{3}}$$ time and subpolynomial space. 2. We show how indirect diagonalization leads to time-space lower bounds for computation with bounded nondeterminism. For both the random access and multitape Turing machine models, we prove that for all k ≥ 1, there is a constant c k > 1 such that linear time with n 1/k nondeterministic bits is not contained in deterministic $$n^{{c}_{k}}$$ time with subpolynomial space. This is used to prove that satisfiability of Boolean circuits with n inputs and n k size cannot be solved by deterministic multitape Turing machines running in $${n^{{k \cdot {c}}_{k}}}$$ time and subpolynomial space. Birkhäuser Verlag, Basel, 2007 Time-space tradeoffs nationallicence lower bounds nationallicence polynomial-time hierarchy nationallicence satisfiability nationallicence diagonalization nationallicence bounded nondeterminism nationallicence 68Q17 nationallicence computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 433-470 1016-3328 15:4<433 2006 15 37 https://doi.org/10.1007/s00037-007-0221-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-007-0221-1 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Williams Ryan Computer Science Department, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 433-470 1016-3328 15:4<433 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer