Sheaf cohomology is \(\#\)P-hard
type: Item
instance of: scholarly article
title: Sheaf cohomology is \(\#\)P-hard
zbMATH Open document ID: 0940.68065
author: Eric Bach
published in: Journal of Symbolic Computation
publication date: 2000-07-16T00:00:00Z
review text: The author proves that computing the dimensions of the cohomology groups of a coherent sheaf on projective space is \(\#\text{P}\)-hard. The proof is based on that statisfiability problems for some Boolean formulas is NP-complete [see \textit{M. R. Garey} and \textit{D. S. Johnson}, ``Computers and Intractability'' (1979; Zbl 0411.68039)] and on that counting their satisfying assignments is \(\#\text{P}\)-complete [see \textit{L. G. Valiant}, Theor. Comput. Sci. 8, 189-201 (1979; Zbl 0415.68008) and J. SIAM Comput. 8, 410-121 (1979; Zbl 0419.68082)]. Then, considering coherent sheaves on projective space, specified by giving a matrix of homogeneous polynomials, the author deduces by means of an example in characteristic 2, that there is no polynomial time algorithm to decide whether a sheaf cohomology group vanishes unless \(\text{P}= \text{NP}\) and that there is no polynomial time algorithm to compute the dimension of a sheaf cohomology group unless \(\text{P}=\#\text{P}\). The computation of the Euler characteristic of sheaves (defined as the alternating sums of dimensions) is also hard for Valiant's complexity class \(\#\text{P}\).
reviewed by: Juan Sabia
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 14F20
Mathematics Subject Classification ID: 14Q99
Mathematics Subject Classification ID: 14F05
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 1275081
zbMATH Keywords: Euler characteristic
zbMATH Keywords: dimensions of the cohomology groups of a coherent
MaRDI profile type: Publication
full work available at URL: jsco.1998.0261
OpenAlex ID: W1999714795
DOI: 10.1006/JSCO.1998.0261
description: scientific article; zbMATH DE number 1275081