Sparse NP-complete problems over the reals with addition

An analog of Mahaney's Theorem was shown, stating that there is no sparse N P-complete problem over the reals with addition and equality - here sparse is defined in terms of dimension. We extend this to the case of the Turing reduction, then turn our attention toward the ordered case where it is show n that such sparse Turing-complete languages do exist. At last, we formulat e a conjecture concerning the case of the many-one reduction. (C) 2001 Else vier Science B.V. All rights reserved.