The monotone and planar circuit value problems are log space complete for P

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The monotone and planar circuit value problems are log space complete for P

Full text

Pdf (159 KB)

Source

ACM SIGACT News archive
Volume 9 , Issue 2 (Summer 1977) table of contents

Pages: 25 - 29

Year of Publication: 1977

ISSN:0163-5700

Author

Leslie M. Goldschlager

University of Toronto

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 37, Citation Count: 19

Additional Information:

references cited by collaborative colleagues

Tools and Actions:	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/1008354.1008356 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	"Cook, S. A., "An Observation on Time-Storage Trade Off" JCSS, vol. 9, No. 3, Dec. 1974 (308--316).
	2	Neil D. Jones , William T. Laaser, Complete problems for deterministic polynomial time, Proceedings of the sixth annual ACM symposium on Theory of computing, p.40-46, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803883]
	3	Richard E. Ladner, The circuit value problem is log space complete for P, ACM SIGACT News, v.7 n.1, p.18-20, January 1975 [doi>10.1145/990518.990519]
	4	Larry Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, v.5 n.3, p.19-25, July 1973 [doi>10.1145/1008293.1008294]

CITED BY 19

	M. Atallah , P. Callahan , M. Goodrich, P-complete geometric problems, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.317-326, July 02-06, 1990, Island of Crete, Greece
	Vijaya Ramachandran , Honghua Yang, An efficient parallel algorithm for the general planar monotone circuit value problem4, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.622-631, January 23-25, 1994, Arlington, Virginia, United States
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	H. Venkateswaran, Properties that characterize LOGCFL, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.141-150, January 1987, New York, New York, United States
	Peter Varman , Kshitij Doshi, Improved parallel algorithms for the depth-first search and monotone circuit value problems, Proceedings of the 15th annual conference on Computer Science, p.175-182, February 1987, St. Louis, Missouri, United States
	Albert G. Greenberg , Boris D. Lubachevsky , Li-C. Wang, Experience in massively parallel discrete event simulation, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.193-202, June 30-July 02, 1993, Velen, Germany
	S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States
	Alexander Okhotin, A recognition and parsing algorithm for arbitrary conjunctive grammars, Theoretical Computer Science, v.302 n.1-3, p.365-399, 13 June 2003
	Jeffrey Scott Vitter , Roger A. Simons, Parallel algorithms for unification and other complete problems in p, Proceedings of the 1984 annual conference of the ACM on The fifth generation challenge, p.75-84, January 1984
	Lane A. Hemaspaandra, SIGACT news complexity theory column 42, ACM SIGACT News, v.34 n.4, December 2003
	Markus Holzer , Waltraud Holzer, Tantrix ^TM rotation puzzles are intractable, Discrete Applied Mathematics, v.144 n.3, p.345-358, 15 December 2004
	A. K. Dewdney, Logic circuits in the plane: minimal crossovers, ACM SIGACT News, v.10 n.3, p.38-48, Winter 1979
	J. A. Makowsky , J. P. Mariño, Tree-width and the monadic quantifier hierarchy, Theoretical Computer Science, v.303 n.1, p.157-170, 28 June 2003
	Stephen Travers, The complexity of membership problems for circuits over sets of integers, Theoretical Computer Science, v.369 n.1, p.211-229, 15 December 2006
	Michael Wooldridge , Paul E. Dunne, The complexity of agent design problems: Determinism and history dependence, Annals of Mathematics and Artificial Intelligence, v.45 n.3-4, p.343-371, December 2005
	N. D. Dendris , L. M. Kirousis , Y. C. Stamatiou , D. M. Thilikos, On Parallel Partial Solutions and Approximation Schemesfor Local Consistency in Networks of Constraints, Constraints, v.5 n.3, p.251-273, July 2000
	I Parberry, Parallel speedup of sequential machines: a defense of parallel computation thesis, ACM SIGACT News, v.18 n.1, p.54-67, Summer 1986
	Dorothea Baumeister , Jörg Rothe, Satisfiability Parsimoniously Reduces to the Tantrix™ Rotation Puzzle Problem, Fundamenta Informaticae, v.91 n.1, p.35-51, January 2009
	Thomas Eiter , Michael Fink , Hans Tompits , Stefan Woltran, Complexity results for checking equivalence of stratified logic programs, Proceedings of the 20th international joint conference on Artifical intelligence, p.330-335, January 06-12, 2007, Hyderabad, India

Collaborative Colleagues:

Leslie M. Goldschlager: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player