The complexity of semilinear problems in succinct representation

DOI10.1007/S00037-006-0213-6MaRDI QIDQ862341zbMATH OpenOpenAlexWikidataFDO

Authors Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois

Publication date 24 January 2007

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-006-0213-6

zbMATH Keywords

semilinear setscomplete problemsBSS additive model

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Fundamentals of Computation Theory
• On the complexity of semidefinite programs
• On Computational Complexity of Semilinear Varieties
• scientific article; zbMATH DE number 219271
• scientific article; zbMATH DE number 4001882
• The complexity of combinatorial problems with succinct input representation
• scientific article; zbMATH DE number 4110112
• The computational complexity of graph problems with succinct multigraph representation
• On the descriptional complexity of operations on semilinear sets
• On time complexity of semidefinite programs arising in polynomial optimization

Cited in

(8)

• On the complexity of semidefinite programs
• Exotic quantifiers, complexity classes, and complete problems
• On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• On the complexity of counting components of algebraic varieties
• The complexity of combinatorial problems with succinct input representation
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 4001882 (Why is no real title available?)

This page was built for publication: The complexity of semilinear problems in succinct representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q862341)