On the complexity of SAT
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 459-464
- https://doi.org/10.1109/sffcs.1999.814618
Abstract
We show that non-deterministic time NTIME(n) is not contained in deterministic time n/sup 2-/spl epsiv// and polylogarithmic space, for any /spl epsiv/>0. This implies that (infinitely often), satisfiability cannot be solved in time O(n/sup 2-/spl epsiv//) 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.Keywords
This publication has 14 references indexed in Scilit:
- Time-space tradeoffs for branching programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Time--Space Tradeoffs For Undirected st-Connectivity on a Graph AutomataSIAM Journal on Computing, 1998
- A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG modelPublished by Association for Computing Machinery (ACM) ,1995
- Near-Optimal Time-Space Tradeoff for Element DistinctnessSIAM Journal on Computing, 1994
- The problem of space invariance for sequential machinesInformation and Computation, 1988
- Two time-space tradeoffs for element distinctnessTheoretical Computer Science, 1986
- Towards separating nondeterminism from determinismTheory of Computing Systems, 1984
- On alternation IIActa Informatica, 1980
- On Time Versus SpaceJournal of the ACM, 1977
- A hierarchy for nondeterministic time complexityJournal of Computer and System Sciences, 1973