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.

Export metadata

Additional Services

Search Google Scholar
Metadaten
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
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.