Complete sets and the polynomial-time hierarchy

DOI10.1016/0304-3975(76)90062-1zbMath0366.02031OpenAlexW1996184580MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20) Hierarchies of computability and definability (03D55)

Related Items (only showing first 100 items - show all)

On the synchronization of semi-traces ⋮ Testing containment of object-oriented conjunctive queries is ∏2p-hard ⋮ Computation models and function algebras ⋮ On counting propositional logic and Wagner's hierarchy ⋮ A System of Interaction and Structure III: The Complexity of BV and Pomset Logic ⋮ On the complexity of robust multi-stage problems with discrete recourse ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity Landscape of Outcome Determination in Judgment Aggregation ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Dot operators ⋮ Computational complexity characterization of protecting elections from bribery ⋮ A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Complexity of the multilevel critical node problem ⋮ Simple characterizations of \(P(\# P)\) and complete problems ⋮ COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA ⋮ On bounded query machines ⋮ On \(\Delta ^ P_ 2\)-immunity ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Complexity of counting the optimal solutions ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ The complexity of combinatorial problems with succinct input representation ⋮ The polynomial hierarchy and a simple model for competitive analysis ⋮ On the complexity of kings ⋮ On hardness of one-way functions ⋮ On helping by robust oracle machines ⋮ More on BPP and the polynomial-time hierarchy ⋮ Characterising equilibrium logic and nested logic programs: Reductions and complexity, ⋮ The complexity of online manipulation of sequential elections ⋮ Weighted Boolean Formula Games ⋮ On the computational complexity of defining sets ⋮ Complexity of Presburger arithmetic with fixed quantifier dimension ⋮ Parallel computation with threshold functions ⋮ Decompositions of nondeterministic reductions ⋮ Index sets and presentations of complexity classes ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ Probabilistic quantifiers and games ⋮ Parameterized complexity classes beyond para-NP ⋮ Subclasses of Presburger arithmetic and the polynomial-time hierarchy ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Axiomatizing physical experiments as oracles to algorithms ⋮ A refinement of the low and high hierarchies ⋮ Autoreducibility, mitoticity, and immunity ⋮ Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting ⋮ Characterizing polynomial complexity classes by reducibilities ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ 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\) ⋮ Model-checking hierarchical structures ⋮ Reasoning about non-immediate triggers in biological networks ⋮ Complexity of Counting the Optimal Solutions ⋮ Optimization problems and the polynomial hierarchy ⋮ Bounded query machines: on NP( ) and NPQUERY( ) ⋮ New developments in structural complexity theory ⋮ Complexity results for modal dependence logic ⋮ A uniform approach to obtain diagonal sets in complexity classes ⋮ The complexity of problems for quantified constraints ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Circuit lower bounds in bounded arithmetics ⋮ An arithmetical characterization of NP ⋮ On counting problems and the polynomial-time hierarchy ⋮ On balanced versus unbalanced computation trees ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ On sets polynomially enumerable by iteration ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Improving Strategies via SMT Solving ⋮ Semigroup automaton structure by homomorphism and domain partition ⋮ Restricted relativizations of probabilistic polynomial time ⋮ A second step toward the strong polynomial-time hierarchy ⋮ On the acceptance power of regular languages ⋮ On quasilinear-time complexity theory ⋮ 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 ⋮ Path-disruption games: bribery and a probabilistic model ⋮ Three \(\sum^ P_ 2\)-complete problems in computational learning theory ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ On the counting complexity of propositional circumscription ⋮ Relativized polynomial hierarchies extending two levels ⋮ On sparse hard sets for counting classes ⋮ An upper bound for the circuit complexity of existentially quantified Boolean formulas ⋮ The role of rudimentary relations in complexity theory ⋮ Computational methods for database repair by signed formulae ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Error-bounded probabilistic computations between MA and AM ⋮ On languages specified by relative acceptance ⋮ A second step toward the polynomial hierarchy ⋮ A note on sparse sets and the polynomial-time hierarchy ⋮ Probabilistic complexity classes and lowness ⋮ Efficient Probabilistically Checkable Debates ⋮ Definability, decidability, complexity ⋮ Bounding queries in the analytic polynomial-time hierarchy ⋮ Reasoning with different levels of uncertainty ⋮ Linear connectivity problems in directed hypergraphs ⋮ Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting ⋮ Properties of uniformly hard languages

Cites Work

This page was built for publication: Complete sets and the polynomial-time hierarchy