Characterizing co-NL by a group action

摘要

In a recent paper, Girard (2012) proposed to use his recent construction of a geometry ofrninteraction in the hyperfinite factor (Girard 2011) in an innovative way to characterizerncomplexity classes. We begin by giving a detailed explanation of both the choices and thernmotivations of Girard’s definitions. We then provide a complete proof that the complexityrnclass co-NL can be characterized using this new approach. We introduce the nondeterministicrnpointer machine as a technical tool, a concrete model to compute algorithms.