Abstract:
The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets: 1. E = UE if, and only if, all functions f: {1}^* \to \Sigma^* in NPSV_g lie in FP. 2. E = NE if, and only if, all functions f: {1}^* \to \Sigma^* in NPFewV lie in FP. 3. E = E^NP if, and only if, all functions f: {1}^* \to \Sigma^* in OptP lie in FP. 4. E = E^NP if, and only if, all standard left cuts in NP lie in P. 5. E = EH if, and only if, PH \cap P/poly = P. We apply these results to the immunity of P-selective sets. It is known that they can be bi-immune, but not \Pi_2^p/1-immune. Their immunity is closely related to top-Toda languages, whose complexity we link to the exponential realm, and also to king languages. We introduce the new notion of superkings, which are characterized in terms of \exists\forall-predicates rather than \forall\exists-predicates, and show that king languages cannot be \Sigma_2^p-immune. As a consequence, P-selective sets cannot be \Sigma_2^/1-immune and, if E^NP^NP = E, not even P/1-immune.