×

zbMATH — the first resource for mathematics

Characterizing co-NL by a group action. (English) Zbl 1362.68084
Summary: In a recent paper, J.-Y. Girard [in: Epistemology versus ontology. Essays on the philosophy and foundations of mathematics in honour of Per Martin-Löf. Based on the conference, “Philosophy and foundations of mathematics: Epistemological and ontological aspects”, Uppsala, Sweden, May 5–8, 2009. Dordrecht: Springer. 243–263 (2012; Zbl 1314.03051)] proposed to use his recent construction of a geometry of interaction in the hyperfinite factor [loc. cit.] in an innovative way to characterize complexity classes. We begin by giving a detailed explanation of both the choices and the motivations of Girard’s definitions. We then provide a complete proof that the complexity class co-NL can be characterized using this new approach. We introduce the nondeterministic pointer machine as a technical tool, a concrete model to compute algorithms.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03F52 Proof-theoretic aspects of linear logic and other substructural logics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1016/j.apal.2012.04.005 · Zbl 1252.03143
[2] Bulletin of the EATCS 33 pp 96– (1987)
[3] C*-Algebras and Operator Theory (1990)
[4] DOI: 10.1016/j.tcs.2003.10.018 · Zbl 1079.03057
[5] DOI: 10.1016/S0049-237X(08)70271-4
[6] DOI: 10.1007/978-3-642-37075-5_21 · Zbl 1260.68099
[7] DOI: 10.1016/S0890-5401(03)00010-5 · Zbl 1019.03039
[8] Mathematica Scandinavia 37 pp 271– (1975) · Zbl 0304.46044
[9] Logical Methods in Computer Science 6 pp 1– (2010)
[10] DOI: 10.1007/978-94-007-4435-6_12 · Zbl 1314.03051
[11] DOI: 10.1016/j.tcs.2010.12.016 · Zbl 1230.03093
[12] A Course in Functional Analysis (1990) · Zbl 0706.46003
[13] Fundamenta Informaticae 45 pp 1– (2001)
[14] Electronic Proceedings in Theoretical Computer Science 75 pp 15– (2011)
[15] Computational Complexity: A Modern Approach (2009) · Zbl 1193.68112
[16] Theory of Operator Algebras 3 (2003)
[17] Theory of Operator Algebras 2 (2003)
[18] Theory of Operator Algebras 1 (2001)
[19] DOI: 10.1147/rd.105.0388 · Zbl 0168.01303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.