Complete sets and the polynomial-time hierarchy
From MaRDI portal
Publication:1241440
DOI10.1016/0304-3975(76)90062-1zbMath0366.02031MaRDI QIDQ1241440
Publication date: 1977
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90062-1
68Q25: Analysis of algorithms and problem complexity
03D20: Recursive functions and relations, subrecursive hierarchies
03D55: Hierarchies of computability and definability
Related Items
Immunity and Simplicity for Exact Counting and Other Counting Classes, A refinement of the low and high hierarchies, On balanced versus unbalanced computation trees, UP and the low and high hierarchies: A relativized separation, On the acceptance power of regular languages, On quasilinear-time complexity theory, Three \(\sum^ P_ 2\)-complete problems in computational learning theory, On sets polynomially enumerable by iteration, Semigroup automaton structure by homomorphism and domain partition, Restricted relativizations of probabilistic polynomial time, Results on communication complexity classes, On polynomial time one-truth-table reducibility to a sparse set, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets, On sparse hard sets for counting classes, Bounding queries in the analytic polynomial-time hierarchy, Simple characterizations of \(P(\# P)\) and complete problems, Locating \(P\)/poly optimally in the extended low hierarchy, More on BPP and the polynomial-time hierarchy, Complexity of Presburger arithmetic with fixed quantifier dimension, Index sets and presentations of complexity classes, On the power of alternation on reversal-bounded alternating Turing machines with a restriction, Nondeterministic stack register machines, Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\), The closure of monadic NP, Definability, decidability, complexity
