The complexity of semilinear problems in succinct representation

DOI10.1007/S00037-006-0213-6zbMATH Open1113.68057OpenAlexW2043457210WikidataQ57733201 ScholiaQ57733201MaRDI QIDQ862341FDOQ862341

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

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

zbMATH Keywords

semilinear setscomplete problemsBSS additive model

Mathematics Subject Classification ID

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

Cited In (8)

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

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)