On the complexity of Quadratic Programming in real number models of computation
- The complexity of linearly constrained (nonconvex) quadratic programming is analyzed within the framework of real number models, namely the one of Blum, Shub, and Smale and its modification recently introduced by Koiran (“weak BSS-model”). In particular we show that this problem is not NP-complete in the Koiran setting. Applications to the (full) BSS-model are discussed.
Author: | Klaus MeerGND |
---|---|
URL: | http://www.sciencedirect.com/science/article/pii/0304397594000700 |
DOI: | https://doi.org/10.1016/0304-3975(94)00070-0 |
ISSN: | 0304-3975 |
Title of the source (English): | Theoretical Computer Science |
Document Type: | Scientific journal article peer-reviewed |
Language: | English |
Year of publication: | 1994 |
Volume/Year: | 133 |
Issue number: | 1 |
First Page: | 85 |
Last Page: | 94 |
Faculty/Chair: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik |