Paper Info
Title
The Complexity of Semilinear Problems in Succinct Representation
Abstract
We prove completeness results for twenty-three problems in semilinear geometry. These results involve semilinear sets given by addi- tive circuits as input data. If arbitrary real constants are allowed in the circuit, the completeness results are for the Blum-Shub-Smale additive model of computation. If, in contrast, the circuit is constant-free, then the completeness results are for the Turing model of computation. One such result, the PNP(log)-completeness of deciding Zariski irreducibility, exhibits for the first time a problem with a geometric nature complete in this class. Keywords. BSS additive model, semilinear sets, complete problems. Subject classification. 68Q15.
Year
DOI
Venue
2005
10.1007/11537311_42
Computational Complexity
Keywords
Field
DocType
additive model,model of computation
Discrete mathematics,Combinatorics,Irreducible component,Additive model,Irreducibility,Model of computation,Turing machine,Time complexity,Completeness (statistics),Mathematics,Computation
Conference
Volume
Issue
ISSN
15
3
1420-8954
ISBN
Citations 
PageRank 
3-540-28193-2
6
0.54
References 
Authors
25
3
Name
Order
Citations
PageRank
Peter Bürgisser132426.63
Felipe Cucker266668.99
Paulin Jacobé de Naurois3344.98