NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-96-007

On the structure of $\npoly{C}$

Gregorio Malajovich and Klaus Meer
RWTH Aachen
Germany

Abstract
This paper deals with complexity classes $\poly{C}$ and $\npoly{C}$, as they were introduced over the complex numbers by Blum, Shub and Smale.  Under the assumption $\poly{C} \ne \npoly{C}$ the existence of non-complete problems in $\npoly{C}$~, not belonging to $\poly{C}$~, is established.

Download Compressed Postscript
Title page