ECCC-Report TR08-027https://eccc.weizmann.ac.il/report/2008/027Comments and Revisions published for TR08-027en-usTue, 18 Mar 2008 13:23:58 +0200
Paper TR08-027
| Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets |
Till Tantau
https://eccc.weizmann.ac.il/report/2008/027The 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.
Tue, 18 Mar 2008 13:23:58 +0200https://eccc.weizmann.ac.il/report/2008/027