On sparseness, reducibilities, and complexity (Q1779309)

\textit{S. R. Mahaney}'s theorem [J. Comput. Syst. Sci. 25, 130--143 (1982; Zbl 0493.68043)] from complexity theory states for the classes P and NP of sets of words that can be recognized by a Turing machine in deterministic and nondeterministic polynomial time, respectively, that, unless P = NP, there are no sparse sets that are hard for NP under polynomial-time many-one reductions, where a set of words is sparse if it contains at most polynomially many words of any given length. In a context of computations over the reals, as introduced by \textit{L. Blum, M. Shub} and \textit{S. Smale} [Bull. Am. Math. Soc., New Ser. 21, 1--46 (1989; Zbl 0681.03020)], the author considers analogues of Mahaney's theorem, where now a set \(S\) is sparse if, for some constant~\(q\) and all~\(n\), the Zariski closure of the intersection of~\(S\) and~\(\mathbb R^n\) has dimension~\(\log^q n\). For the computation model over the reals that includes addition and equality tests, the author first reviews the result of \textit{H. Fournier} [Theor. Comput. Sci. 255, 607--610 (2001; Zbl 0973.68074)] that there are no sparse definable NP-Turing-hard sets and hence no sparse NP-Turing-complete sets, and then shows that there are sparse NP-Turing-hard sets. Then the author introduces a notion of well-behaved set that comprises the notion of definable set, and, extending previously known results, demonstrates for another specific model of computation, the weak model, that there are no well-behaved sets that are Turing-hard for the analogue of the class NP in the weak model. Finally, the author demonstrates that with respect to various models of computation and reducibilities there are no or at least no well-behaved sparse hard sets for the analogues of the classes P and EXP.