Sheaf cohomology is \(\#\)P-hard (Q1283198)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sheaf cohomology is \(\#\)P-hard |
scientific article |
Statements
Sheaf cohomology is \(\#\)P-hard (English)
0 references
16 July 2000
0 references
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}\).
0 references
Euler characteristic
0 references
dimensions of the cohomology groups of a coherent
0 references