|
NeuroCOLT |
Neural Networks and Computational Learning Theory |
||||||||
|
|
NeuroCOLT
Technical Report NC-TR-94-006 On the complexity of Quadratic Programming in real number models of computation K.
Meer Abstract The complexity of linearly constrained (non-convex) 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.
Download Compressed Postscript
|