RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
From MaRDI portal
Publication:4315092
DOI10.1070/IM1994v042n02ABEH001537zbMath0822.68035OpenAlexW2048383625MaRDI QIDQ4315092
Publication date: 6 December 1994
Published in: Russian Academy of Sciences. Izvestiya Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1070/im1994v042n02abeh001537
Related Items
A characterization of the leaf language classes ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Optimal proof systems imply complete sets for promise classes ⋮ Complexity limitations on quantum computation ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Helping by unambiguous computation and probabilistic computation ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Leaf languages and string compression ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Functions computable in polynomial space ⋮ Machines that can output empty words ⋮ Dot operators ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Relating polynomial time to constant depth ⋮ SELF-SPECIFYING MACHINES ⋮ A reducibility for the dot-depth hierarchy ⋮ Reducing the number of solutions of NP functions
