Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets. Bürgisser, P. & Cucker, F. In In Proceedings of 36th STOC, pages 475-485, Chicago, 2004. ![Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets [link]](https://bibbase.org/img/filetypes/link.svg "link")
2 ![Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex We define counting classes $#P_{\mathbb R}$ and $#P_{\mathbb C}$ in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over $\mathbb R$, or of systems of polynomial equalities over $\mathbb C$, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over $\mathbb R$) and algebraic sets (over $\mathbb C$). We prove that the problem to compute the Euler characteristic of semialgebraic sets is $FP_{\mathbb R}^{#P_{\mathbb R}}$-complete, and that the problem to compute the geometric degree of complex algebraic sets is $FP_{\mathbb C}^{#P_{\mathbb C}}$-complete. We also define new counting complexity classes in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving , for all $k$ in $N$, the FPSPACE-hardness of the problem of computing the $k$-th Betti number of the set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology.
@INPROCEEDINGS{BC-Counting-Complexity-Classes-For-Numeric-Computations-Ii-Algebraic-And-Semialgebraic-Sets-1,
TITLE={Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets},
URL2={http://www.sciencedirect.com/science/article/pii/S0885064X05001081},
YEAR={2004},
AUTHOR={Peter Bürgisser and Felipe Cucker},
BOOKTITLE={In Proceedings of 36th STOC},
URL={http://www3.math.tu-berlin.de/algebra/work/p04-buergisser.pdf},
PAGES={475-485},
ABSTRACT={We define counting classes $\#P_{\mathbb R}$ and $\#P_{\mathbb C}$ in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over $\mathbb R$, or of systems of polynomial equalities over $\mathbb C$, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over $\mathbb R$) and algebraic sets (over $\mathbb C$). We prove that the problem to compute the Euler characteristic of semialgebraic sets is $FP_{\mathbb R}^{\#P_{\mathbb R}}$-complete, and that the problem to compute the geometric degree of complex algebraic sets is $FP_{\mathbb C}^{\#P_{\mathbb C}}$-complete. We also define new counting complexity classes in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving , for all $k$ in $N$, the FPSPACE-hardness of the problem of computing the $k$-th Betti number of the set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology. },
REVIEWED={True},
ADDRESS={Chicago}
}
Downloads: 0
{"_id":"pwAmPJi7Ps8da8Xu2","bibbaseid":"brgisser-cucker-countingcomplexityclassesfornumericcomputationsiialgebraicandsemialgebraicsets-2004","downloads":0,"creationDate":"2017-01-04T12:11:10.533Z","title":"Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets","author_short":["Bürgisser, P.","Cucker, F."],"year":2004,"bibtype":"inproceedings","biburl":"http://www3.math.tu-berlin.de/algebra/static/papers.parsed.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets","url2":"http://www.sciencedirect.com/science/article/pii/S0885064X05001081","year":"2004","author":[{"firstnames":["Peter"],"propositions":[],"lastnames":["Bürgisser"],"suffixes":[]},{"firstnames":["Felipe"],"propositions":[],"lastnames":["Cucker"],"suffixes":[]}],"booktitle":"In Proceedings of 36th STOC","url":"http://www3.math.tu-berlin.de/algebra/work/p04-buergisser.pdf","pages":"475-485","abstract":"We define counting classes $#P_{\\mathbb R}$ and $#P_{\\mathbb C}$ in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over $\\mathbb R$, or of systems of polynomial equalities over $\\mathbb C$, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over $\\mathbb R$) and algebraic sets (over $\\mathbb C$). We prove that the problem to compute the Euler characteristic of semialgebraic sets is $FP_{\\mathbb R}^{#P_{\\mathbb R}}$-complete, and that the problem to compute the geometric degree of complex algebraic sets is $FP_{\\mathbb C}^{#P_{\\mathbb C}}$-complete. We also define new counting complexity classes in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving , for all $k$ in $N$, the FPSPACE-hardness of the problem of computing the $k$-th Betti number of the set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology. ","reviewed":"True","address":"Chicago","bibtex":"@INPROCEEDINGS{BC-Counting-Complexity-Classes-For-Numeric-Computations-Ii-Algebraic-And-Semialgebraic-Sets-1,\r\n TITLE={Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets},\r\n URL2={http://www.sciencedirect.com/science/article/pii/S0885064X05001081},\r\n YEAR={2004},\r\n AUTHOR={Peter Bürgisser and Felipe Cucker},\r\n BOOKTITLE={In Proceedings of 36th STOC},\r\n URL={http://www3.math.tu-berlin.de/algebra/work/p04-buergisser.pdf},\r\n PAGES={475-485},\r\n ABSTRACT={We define counting classes $\\#P_{\\mathbb R}$ and $\\#P_{\\mathbb C}$ in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over $\\mathbb R$, or of systems of polynomial equalities over $\\mathbb C$, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over $\\mathbb R$) and algebraic sets (over $\\mathbb C$). We prove that the problem to compute the Euler characteristic of semialgebraic sets is $FP_{\\mathbb R}^{\\#P_{\\mathbb R}}$-complete, and that the problem to compute the geometric degree of complex algebraic sets is $FP_{\\mathbb C}^{\\#P_{\\mathbb C}}$-complete. We also define new counting complexity classes in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving , for all $k$ in $N$, the FPSPACE-hardness of the problem of computing the $k$-th Betti number of the set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology. },\r\n REVIEWED={True},\r\n ADDRESS={Chicago}\r\n}\r\n\r\n","author_short":["Bürgisser, P.","Cucker, F."],"key":"BC-Counting-Complexity-Classes-For-Numeric-Computations-Ii-Algebraic-And-Semialgebraic-Sets-1","id":"BC-Counting-Complexity-Classes-For-Numeric-Computations-Ii-Algebraic-And-Semialgebraic-Sets-1","bibbaseid":"brgisser-cucker-countingcomplexityclassesfornumericcomputationsiialgebraicandsemialgebraicsets-2004","role":"author","urls":{"2":"http://www.sciencedirect.com/science/article/pii/S0885064X05001081","Paper":"http://www3.math.tu-berlin.de/algebra/work/p04-buergisser.pdf"},"downloads":0,"html":""},"search_terms":["counting","complexity","classes","numeric","computations","algebraic","semialgebraic","sets","bürgisser","cucker"],"keywords":[],"authorIDs":[],"dataSources":["mFLw2PzriqAWWFuqX"]}