caa a22 4500 467909628 CHVBK 20180406152845.0 cr unu---uuuuu 170328e20061001xx s 000 0 eng 10.1007/s00037-006-0213-6 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0213-6 The complexity of semilinear problems in succinct representation [Elektronische Daten] [Peter Bürgisser, Felipe Cucker, Paulin de Naurois] Abstract.: We prove completeness results for twenty-three problems in semilinear geometry. These results involve semilinear sets given by additive 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. Birkhäuser Verlag, Basel, 2006 BSS additive model nationallicence semilinear sets nationallicence complete problems nationallicence 68Q15 nationallicence Bürgisser Peter Department of Mathematics, University of Paderborn, D-33095, Paderborn, Germany aut Cucker Felipe Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong aut de Naurois Paulin LORIA, 615 rue du Jardin Botanique, BP 101, 54602, Villers-lès-Nancy Cedex, Nancy, France aut computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/3(2006-10-01), 197-235 1016-3328 15:3<197 2006 15 37 https://doi.org/10.1007/s00037-006-0213-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0213-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bürgisser Peter Department of Mathematics, University of Paderborn, D-33095, Paderborn, Germany aut NATIONALLICENCE 700 1- Cucker Felipe Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong aut NATIONALLICENCE 700 1- de Naurois Paulin LORIA, 615 rue du Jardin Botanique, BP 101, 54602, Villers-lès-Nancy Cedex, Nancy, France aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/3(2006-10-01), 197-235 1016-3328 15:3<197 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer