NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-96-051

Complexity and Dimension

Felipe Cucker
City University of Hong Kong

Pascal Koiran
Ecole Normale Superieure
Lyon
France

Martin Matamala
Universidad de Chile
Chile

Abstract
In this note we define a notion of sparseness for subsets of $\Ri$ and we prove that there are no sparse $\NPadd$-hard sets. Here we deal with additive machines which branch on equality tests of the form $x=y$ and $\NPadd$ denotes the corresponding class of sets decidable in nondeterministic polynomial time. Note that this result implies the separation $\Padd\not=\NPadd$ already known.

Download Compressed Postscript