IEEE - Institute of Electrical and Electronics Engineers, Inc. - Counting and addition cannot express deterministic transitive closure

Proceedings. 14th Symposium on Logic in Computer Science

Author(s): Ruhl, M.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 January 1999
Conference Location: Trento, Italy, Italy
Conference Date: 5 July 1999
Page(s): 326 - 334
ISBN (Paper): 0-7695-0158-3
ISSN (Paper): 1043-6871
DOI: 10.1109/LICS.1999.782627
Regular:

An important open question in complexity theory is whether the circuit complexity class TC/sup 0/ is (strictly) weaker than LOGSPACE. This paper considers this question from the viewpoint of... View More

Advertisement