More Web Proxy on the site http://driver.im/

Article

On the Complexity of SAT

Authors:

Richard J. Lipton,

Anastasios ViglasAuthors Info & Claims

FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science

Page 459

Published: 17 October 1999 Publication History

Abstract

In this work we show that non-deterministic time NTIME(n) is not contained in deterministic time \math and poly-logarithmic space, for any \math. This implies that (infinitely often) satisfiability cannot be solved in time \math and poly-logarithmic space. A similar result is presented for uniform circuits; a log-space uniform circuit of poly-logarithmic width computing satisfiability requires infinitely often almost quadratic size.

References

[1]

G. Barnes and J. A. Edmonds. Time-space lower bounds for directed st-connectivity on graph automata models. SIAM Journal on Computing, 27(4):1190-1202, Aug. 1998.

[2]

P. Beame. A general sequential time-space tradeoff for finding unique elements. SIAM Journal on Computing, 20(2):270-277, Apr. 1991.

[3]

P. Beame, M. Saks, and J. S. Thathachar. Time-space tradeoffs for branching programs. In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), pages 254-263, 1998.

[4]

S. A. Cook. A hierarchy for nondeterministic time complexity. Journal of Computer and System Sciences, 7(4):343- 353, Aug. 1973.

[5]

J. Edmonds and C. K. Poon. A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 147-156, Las Vegas, Nevada, 29 May-1 June 1995.

[6]

J. A. Edmonds. Time-space tradeoffs for undirected st- connectivity on a graph automata. SIAM Journal on Computing, 27(5):1492-1513, Oct. 1998.

[7]

L. Fortnow. Nondeterministic polynomial time versus nondeterministic logarithmic space: Time-space tradeoffs for satisfiability. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC-97), pages 52- 60, Los Alamitos, June24-27 1997. IEEE Computer Society.

[8]

Y. Gurevich and S. Shelah. Nearly linear time. In A. R. Meyer and M. A. Taitslin, editors, Proceedings of the Symposium on Logical Foundations of Computer Science, volume 363 of LNCS, pages 108-118, Berlin, July 1989. Springer.

[9]

Y. Gurevich and S. Shelah. Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space. Journal of the ACM, JACM, 37(3):674-687, July 1990.

[10]

J. Hopcroft, W. Paul, and L. Valiant. On time versus space. Journal of the ACM., 24(2):332-337, Apr. 1977.

[11]

R. Kannan. Towards separating nondeterminism from determinism. Mathematical Systems Theory, 17(1):29-45, Apr. 1984.

[12]

M. Karchmer. Two time-space tradeoffs for element distinctness. Theoretical Computer Science, 47(3):237-246, 1986.

[13]

W. J. Paul, N. Pippenger, E. Szemerédi, and W. T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In 24th Annual Symposium on Foundations of Computer Science, pages 429-438, Tucson, Arizona, 7-9 Nov. 1983. IEEE.

[14]

W. J. Paul and R. Reischuk. On alternation II. A graph theoretic approach to determinism versus nondeterminism. Acta Informatica, 14:391-403, 1980.

[15]

C. Slot and P. van Emde Boas. The problem of space invariance for sequential machines. Information and Computation, 77(2):93-122, May 1988.

Digital Library

[16]

A. C.-C. Yao. Near-optimal time-space tradeoff for element distinctness. SIAM Journal on Computing, 23(5):966-975, Oct. 1994.

Cited By

Williams R(2013)Alternation-Trading Proofs, Linear Programming, and Lower BoundsACM Transactions on Computation Theory10.1145/2493246.24932495:2(1-49)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1145/2493246.2493249
Fortnow LLipton Rvan Melkebeek DViglas A(2005)Time-space lower bounds for satisfiabilityJournal of the ACM (JACM)10.1145/1101821.110182252:6(835-865)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1145/1101821.1101822
van Melkebeek DRaz R(2005)A time lower bound for satisfiabilityTheoretical Computer Science10.1016/j.tcs.2005.09.020348:2(311-320)Online publication date: 8-Dec-2005
https://dl.acm.org/doi/10.1016/j.tcs.2005.09.020
Show More Cited By

On the Complexity of SAT
1. Theory of computation

Recommendations

Inductive Time-Space Lower Bounds for Sat and Related Problems

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 ...
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs

We provide some evidence that Unique k-SAT is as hard to solve as general k-SAT, where k-SAT denotes the satisfiability problem for k-CNFs with at most k literals in each clause and Unique k-SAT is the promise version where the given formula has 0 or 1 ...
The Efficiency of Resolution and Davis--Putnam Procedures

We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisfiable. First, building on the work of Clegg, Edmonds, and Impagliazzo in [Proceedings of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science

October 1999

ISBN:0769504094

Copyright © Copyright (c) 1998 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 17 October 1999

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Williams R(2013)Alternation-Trading Proofs, Linear Programming, and Lower BoundsACM Transactions on Computation Theory10.1145/2493246.24932495:2(1-49)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1145/2493246.2493249
Fortnow LLipton Rvan Melkebeek DViglas A(2005)Time-space lower bounds for satisfiabilityJournal of the ACM (JACM)10.1145/1101821.110182252:6(835-865)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1145/1101821.1101822
van Melkebeek DRaz R(2005)A time lower bound for satisfiabilityTheoretical Computer Science10.1016/j.tcs.2005.09.020348:2(311-320)Online publication date: 8-Dec-2005
https://dl.acm.org/doi/10.1016/j.tcs.2005.09.020
Diehl Svan Melkebeek D(2005)Time-space lower bounds for the polynomial-time hierarchy on randomized machinesProceedings of the 32nd international conference on Automata, Languages and Programming10.1007/11523468_79(982-993)Online publication date: 11-Jul-2005
https://dl.acm.org/doi/10.1007/11523468_79
Beame PSaks MSun XVee E(2003)Time-space trade-off lower bounds for randomized computation of decision problemsJournal of the ACM (JACM)10.1145/636865.63686750:2(154-195)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1145/636865.636867
Tourlakis I(2001)Time Space Tradeoffs for SAT on Nonuniform MachinesJournal of Computer and System Sciences10.1006/jcss.2001.176763:2(268-287)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1006/jcss.2001.1767

View Options

View options

Media

Figures

Other

Tables

View Table of Contents