×

The complexity and distribution of hard problems. (English) Zbl 0827.68043

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\).

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI