Sparse NP-complete problems over the reals with addition
An analog of Mahaney's Theorem was shown, stating that there is no sparse NP-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 shown that such sparse Turing-complete languages do exist. At last, we formulate a conjecture concerning the case of the many-one reduction. (C) 2001 Elsevier Science B.V. All rights reserved.
sparse sets real complexity knapsack