Relativizations comparing NP and exponential time

DOI10.1016/S0019-9958(83)80058-8zbMath0562.68034OpenAlexW1983856665MaRDI QIDQ3675521

Homer, Steven, William I. Gasarch

Publication date: 1983

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(83)80058-8

zbMATH Keywords

exponential timeoraclesimmunenondeterministic polynomial timerelativized complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Almost every set in exponential time is P-bi-immune, Simultaneous strong separations of probabilistic and unambiguous complexity classes, Simplicity, immunity, relativizations and nondeterminism, A second step toward the strong polynomial-time hierarchy, A Logic for PTIME and a Parameterized Halting Problem, Almost every set in exponential time is P-bi-immune, Towards the Actual Relationship Between NP and Exponential Time, Bi-immune sets for complexity classes