The complexity of tensor calculus
type: Item
instance of: scholarly article
title: The complexity of tensor calculus
zbMATH Open document ID: 1033.15025
author: Carsten Damm
author: Pierre McKenzie
author: Markus Holzer
published in: Computational Complexity
publication date: 2003-11-17T00:00:00Z
review text: The authors study the word problem generalized to multilinear algebra expressed by tensors. They show that basic tensor calculus not only captures natural complexity classes in simple ways, but it yields simpler unified proofs of nonuniform inclusions formerly scattered in the literature. Their results concern tensors over semirings, including the Boolean semiring \(B= (\{0, 1\},\vee,\wedge)\), the fields of characteristic 2, and the natural numbers \(N= (\{0,1,\dots\},+,\bullet)\). The structure of the paper is as follows. In Section 2 the authors introduce the complexity classes needed in later sections. They also introduce the terminology and basic parsing techniques for tensor formulas. To support intuition they strictly base all the formalism on matrices rather than tensors. This is based on connections between multi-index tensor notation and two-index matrix notation, clarified in Section 3. In Section 4 they give a polytime algorithm to construct a tensor formula which evaluates to the permanent of a square matrix. Then in Section 5 they introduce algebraic Turning machines, and use this model in Section 6 to prove their completeness results. In Section 7 they give a unified and intuitive proof for the existence of nonuniform simulations between Boolean and arithmetic complexity classes. In the last section, they conclude and discuss related results.
Mathematics Subject Classification ID: 15A69
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 2004972
zbMATH Keywords: Tensor formula
zbMATH Keywords: permanent
zbMATH Keywords: complexity
zbMATH Keywords: counting classes
zbMATH Keywords: completeness
zbMATH Keywords: algebraic Turing machine
zbMATH Keywords: word problem
zbMATH Keywords: multilinear algebra
zbMATH Keywords: tensor calculus
zbMATH Keywords: Boolean semiring
zbMATH Keywords: polytime algorithm
reviewed by: Yueh-er Kuo
MaRDI profile type: Publication
full work available at URL: s00037-000-0170-4
OpenAlex ID: W3167560924
DOI: 10.1007/S00037-000-0170-4
description: scientific article; zbMATH DE number 2004972