The Boolean formula value problem is in ALOGTIME

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Boolean formula value problem is in ALOGTIME

Full text

Pdf (1.14 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents

New York, New York, United States

Pages: 123 - 131

Year of Publication: 1987

ISBN:0-89791-221-7

Author

S. R. Buss

Department of Mathematics, University of California, Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 30, Citation Count: 13

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/28395.28409 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	A. BORODIN, On ~,elating time and space to size and depth, SIAM J. Comput., 6 (1977), pp. 733-744.
	2	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	3	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	4	Stephen A. Cook, Deterministic CFL's are accepted simultaneously in polynomial time and log squared space, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.338-345, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804426]
	5	Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
	6	M. DOWO, Notes on log space representation, 1986, typewritten manuscript.
	7	A. GUPT~, A Fast Parallel Al#orithm for Recognition of Parenthesis Languages, Master's thesis, University of Toronto, January 1985.
	8	J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
	9	O. H. IBARRA, T. JIANG, AND B. RAVIKUMAR, On some lanatlases in NC1 (summa~'!t), 1987, manuscript.
	10	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]
	11	Nancy Lynch, Log Space Recognition and Translation of Parenthesis Languages, Journal of the ACM (JACM), v.24 n.4, p.583-590, Oct. 1977 [doi>10.1145/322033.322037]
	12	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	13	G. L. MILLER AND J. H. REIF, Parallel tree contraction and its application, in Proceedings of the 26-th IEEE Symposium on Foundations of Computer Science, 1985, pp. 478-489.
	14	V. RAMACHANOa^N, Restraeturin9 formula trees, May 1986, unpublished manuscript.
	15	W. L. Ruzzo, On uniform circuit complexit~l, J. Comput. System Sci., 22 (1981), pp. 365-383.
	16	John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
	17	P. M. SPIRA, On time hardware complezit!l tradeoffs for Boolean functions, in Proceedings of the Fourth Hawaii International Sympo6ium on System Sciences, 1971, pp. 525-527.
	18	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

CITED BY 13

	Paris Kanellakis, Constraint programming and database languages: a tutorial, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.46-53, May 22-25, 1995, San Jose, California, United States
	Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States
	Carsten Damm , Markus Holzer , Pierre McKenzie, The complexity of tensor calculus, Computational Complexity, v.11 n.1/2, p.54-89, January 2003
	Eric W. Allender, P-uniform circuit complexity, Journal of the ACM (JACM), v.36 n.4, p.912-928, Oct. 1989
	David A. Mix Barrington , Denis Thérien, Finite monoids and the fine structure of NC1, Journal of the ACM (JACM), v.35 n.4, p.941-952, Oct. 1988
	Markus Holzer, Multi-head finite automata: data-independent versus data-dependent computations, Theoretical Computer Science, v.286 n.1, p.97-116, 6 September 2002
	M. Beaudry , M. Holzer , G. Niemann , F. Otto, McNaughton families of languages, Theoretical Computer Science, v.290 n.3, p.1581-1628, 3 January 2003
	Steven Lindell, A logspace algorithm for tree canonization (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.400-404, May 04-06, 1992, Victoria, British Columbia, Canada
	Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005
	Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California
	Paris Kanellakis, Database querying and constraint programming, ACM SIGACT News, v.25 n.4, p.22-87, Dec. 1994
	Thomas Eiter , Michael Fink , Stefan Woltran, Semantical characterizations and complexity of equivalences in answer set programming, ACM Transactions on Computational Logic (TOCL), v.8 n.3, p.17-es, July 2007
	Martin Beaudry , Markus Holzer, The Complexity of Tensor Circuit Evaluation, Computational Complexity, v.16 n.1, p.60-111, May 2007