Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets
Till Tantau · 2008
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 ⇐ ⇒ all functions f: {1} ∗ → Σ ∗ in NPSVg lie in FP. 2. E = NE ⇐ ⇒ all functions f: {1} ∗ → Σ ∗ in NPFewV lie in FP. 3. E = E NP ⇐ ⇒ all functions f: {1} ∗ → Σ ∗ in OptP lie in FP. 4. E = E NP ⇐ ⇒ all standard left cuts in NP lie in P. 5. E = EH ⇐ ⇒ PH ∩ 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 Π p 2 /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 ∃∀-predicates rather than ∀∃-predicates, and show that king languages cannot be Σ p 2-immune. As a consequence, /1-immune and, if EΣp2 = E, not even P/1-immune. P-selective sets cannot be Σ p 2 1