Time–Space Tradeoffs for SAT on Nonuniform Machines

✍ Scribed by Iannis Tourlakis

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 176 KB
• Volume: 63
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2001.1767

✦ Synopsis

are generalized and combined with an argument for diagonalizing over machines taking n bits of advice on inputs of length n to obtain the first nontrivial time-space lower bounds for SAT on nonuniform machines.

In particular, we show that for any a < 2 and any e > 0, SAT cannot be computed by a random access deterministic Turing machine using n a time, n o(1) space, and o(n 2 /2 -e ) advice nor by a random access deterministic Turing machine using n 1+o(1) time, n 1 -e space, and n 1 -e advice. More generally, we show that if for some e > 0 there exists a random access deterministic Turing machine solving SAT using n a time, n b space, and o(n (a+b)/2 -e ) advice, then a \ 1 2 ( `b2 +8 -b). Lower bounds for computing SAT on random access nondeterministic Turing machines taking sublinear advice are also obtained. Moreover, we show that SAT does not have NC 1 circuits of size n l+o(1) generated by a nondeterministic log-space machine taking n o(1) advice. Additionally, new separations of uniform classes are obtained. We show that for all e > 0 and all rational numbers r \ 1, DTISP(n r , n 1 -e ) is properly contained in NTIME(n r ).