Juedes, David W.; Lutz, Jack H. The complexity and distribution of hard problems. (English) Zbl 0827.68043 SIAM J. Comput. 24, No. 2, 279-295 (1995). Summary: Measure-theoretic aspects of the \(\leq^{\text{P}}_m\)-reducibility structure of the exponential time complexity classes \(\text{E} = \text{DTIME}(2^{\text{linear}})\) and \(\text{E}_2 = \text{DTIME}(2^{\text{polynomial}})\) are investigated. Particular attention is given to the complexity (measured by the size of complexity cores) and distribution (abundance in the sense of measure) of languages that are \(\leq^{\text{P}}_m\)-hard for \(E\) and other complexity classes. Tight upper and lower bounds on the size of complexity cores of hard languages are derived. The upper bound says that the \(\leq^{\text{P}}_m\)-hard languages for E are unusually simple, in the sense that they have smaller complexity cores than most languages in E. It follows that the \(\leq^{\text{P}}_m\)-complete languages for E form a measure 0 subset of E (and similarly in \(\text{E}_2\). This latter fact is seen to be a special case of a more general theorem, namely, that every \(\leq^{\text{P}}_m\)-degree (e.g., the degree of all \(\leq^{\text{P}}_m\)-complete languages for NP) has measure 0 in E and in \(\text{E}_2\). Cited in 2 ReviewsCited in 17 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) Keywords:complexity; distribution PDFBibTeX XMLCite \textit{D. W. Juedes} and \textit{J. H. Lutz}, SIAM J. Comput. 24, No. 2, 279--295 (1995; Zbl 0827.68043) Full Text: DOI