Satisfiability Is Quasilinear Complete in NQL

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Satisfiability Is Quasilinear Complete in NQL

Full text

Pdf (638 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 136 - 145

Year of Publication: 1978

ISSN:0004-5411

Author

C. P. Schnorr

Johann Wolfgang Goethe Universitat, Fachbereich Mathematik, Robert-Mayer-Strasse 6-10, 6 Frankfurt am Main, West Germany and Universitat Frankfurt, Frankfurt am Main, West Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 28, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322047.322060 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	2	Stephen A. Cook, A hierarchy for nondeterministic time complexity, Proceedings of the fourth annual ACM symposium on Theory of computing, p.187-192, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804913]
	3	FISCHER, M J Lectures on network complextty Preprmt, U Frankfurt, 1974
	4	F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
	5	KARP, R M Reduclbthty among combinatorial problems in Complextty of Computer Computattons, R E Miller and J W Thatcher, Eds , Plenum Press, New York, 1972, pp 85-104
	6	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	7	LEVIN, L.A Universal enumeration problems (m Russtan) Problemt Peredaci Informacu, Tom IX, 1972, pp 115-116
	8	SC~NORR, C P The network complexity and the Turmg machine complexity of flmte functtons ACTA Informauca 7 (1976), 95-107
	9	SCnNORR, C P A lower bound on the number of addmons an monotone computations. Theoretical Comptr. Sct 2 (1976), 305-315
	10	Komplexität von Entscheidungsproblemen, Ein Seminar, January 1976

CITED BY 10

	Therese Biedl, Linear reductions of maximum matching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.825-826, January 07-09, 2001, Washington, D.C., United States
	Arnaud Durand , Malika More, Nonerasing, counting, and majority over the linear time hierarchy, Information and Computation, v.174 n.2, p.132-142, May 1 2002
	Harry B. Hunt, III , Madhav V. Marathe , Richard E. Stearns, Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.183-191, July 2001, London, Ontario, Canada
	Richard E. Stearns, Deterministic versus nondeterministic time and lower bound problems, Journal of the ACM (JACM), v.50 n.1, p.91-95, January 2003
	Lance Fortnow , Richard Lipton , Dieter van Melkebeek , Anastasios Viglas, Time-space lower bounds for satisfiability, Journal of the ACM (JACM), v.52 n.6, p.835-865, November 2005
	Ryan Williams, Inductive Time-Space Lower Bounds for Sat and Related Problems, Computational Complexity, v.15 n.4, p.433-470, December 2006
	Kenneth W. Regan , Jie Wang, The quasilinear isomorphism challenge, ACM SIGACT News, v.25 n.3, p.106-113, Sept. 1994
	Kenneth W. Regan, Machine models and linear time complexity, ACM SIGACT News, v.24 n.3, p.5-15, Oct. 1993
	Stephen A. Bloch , Jonathan F. Buss , Judy Goldsmith, How hard are n2-hard problems?, ACM SIGACT News, v.25 n.2, p.83-85, June 1994
	Ryan Williams, Applying practice to theory, ACM SIGACT News, v.39 n.4, December 2008