Name
Abstract | ||
|---|---|---|
We show that non-deterministic time NTIME(n) is not contained in deterministic time n2-ε and polylogarithmic space, for any ε>0. This implies that (infinitely often), satisfiability cannot be solved in time O(n2-ε) and polylogarithmic space. A similar result is presented for uniform circuits; a log-space uniform circuit of polylogarithmic width computing satisfiability requires infinitely often almost quadratic size |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1109/SFFCS.1999.814618 | New York City, NY |
Keywords | Field | DocType |
computability,computational complexity,theorem proving,NTIME,SAT complexity,almost quadratic size,deterministic time,log-space uniform circuit,non-deterministic time,polylogarithmic space,polylogarithmic width,satisfiability,uniform circuits | Discrete mathematics,Combinatorics,Satisfiability,Automated theorem proving,Quadratic equation,Computability,NC,NTIME,Mathematics,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-7695-0409-4 | 21 |
PageRank | References | Authors |
0.93 | 24 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard J. Lipton | 1 | 6412 | 1796.57 |
| Anastasios Viglas | 2 | 197 | 15.97 |