ON THE COMPLEXITY OF QUADRATIC-PROGRAMMING IN REAL NUMBER MODELS OF COMPUTATION

Authors
MEER K
Citation
K. Meer, ON THE COMPLEXITY OF QUADRATIC-PROGRAMMING IN REAL NUMBER MODELS OF COMPUTATION, Theoretical computer science, 133(1), 1994, pp. 85-94
Citations number
20
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
133
Issue
1
Year of publication
1994
Pages
85 - 94
Database
ISI
SICI code
0304-3975(1994)133:1<85:OTCOQI>2.0.ZU;2-W
Abstract
The complexity of linearly constrained (nonconvex) quadratic programmi ng 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 proble m is not NP-complete in the Koiran setting. Applications to the (full) BSS-model are discussed.