2016/02/15 by Mathias Hauptmann, Hauptmann, Mathias · 2 voices
Computer Science · Economics, Econometrics and Finance · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1602.04781
openalex publication_date 2016/02/15 · arxiv published 2016/02/15 · arxiv created 2016/06/03 · arxiv updated 2016/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Under the assumption P=Σ2p, we prove a new variant of the Union Theorem of McCreight and Meyer for the class Σ2p. This yields a union function F which is computable in time F(n)c for some constant c and satisfies P=DTIME(F)=Σ2(F)=Σ2p with respect to a subfamily (Si) of Σ2-machines. We show that this subfamily does not change the complexity classes P and Σ2p. Moreover, a padding construction shows that this also implies DTIME(Fc)=Σ2(Fc). On the other hand, we prove a variant of Gupta's result who showed that DTIME(t)\subsetneqΣ2(t) for time-constructible functions t(n). Our variant of this result holds with respect to the subfamily (Si) of Σ2-machines. We show that these two results contradict each other. Hence the assumption P=Σ2p cannot hold.