Complete sets and the polynomial-time hierarchy

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

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
The complexity of theorem-proving procedures
On the computational power of pushdown automata
Space-bounded reducibility among combinatorial problems
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Infinite exponent partition relations and well-ordered choice
Relativization of the Theory of Computational Complexity
Time- and tape-bounded Turing acceptors and AFLs
The lattices of prefixes and overlaps of traces

Cited In (only showing first 100 items - show all)

An upper bound for the circuit complexity of existentially quantified Boolean formulas
On $\Delta ^ P_ 2$-immunity
Three $\sum^ P_ 2$-complete problems in computational learning theory
Probabilistic quantifiers and games
The closure of monadic NP
On languages specified by relative acceptance
On the power of alternation on reversal-bounded alternating Turing machines with a restriction
Decompositions of nondeterministic reductions
Model-checking hierarchical structures
On the complexity of kings
On balanced versus unbalanced computation trees
Complexity of Presburger arithmetic with fixed quantifier dimension
Results on communication complexity classes
Resource bounded immunity and simplicity
Some connections between bounded query classes and non-uniform complexity.
A second step toward the strong polynomial-time hierarchy
Efficient Probabilistically Checkable Debates
Complexity of counting the optimal solutions
Relativized polynomial hierarchies extending two levels
On sparse hard sets for counting classes
New developments in structural complexity theory
On the counting complexity of propositional circumscription
Polynomial-time 1-Turing reductions from $\#$PH to $\#$P
Autoreducibility, mitoticity, and immunity
A note on complete sets and transitive closure
On helping by robust oracle machines
On the relative complexity of hard problems for complexity classes without complete problems
On the computational complexity of defining sets
The complexity of combinatorial problems with succinct input representation
The complexity of online manipulation of sequential elections
On some natural complete operators
Simple characterizations of $P(\# P)$ and complete problems
On hardness of one-way functions
Parallel computation with threshold functions
On counting problems and the polynomial-time hierarchy
Locating $P$/poly optimally in the extended low hierarchy
Circuit lower bounds in bounded arithmetics
Weighted Boolean Formula Games
Complexity results for modal dependence logic
Error-bounded probabilistic computations between MA and AM
Axiomatizing physical experiments as oracles to algorithms
All superlinear inverse schemes are coNP-hard
More on BPP and the polynomial-time hierarchy
Properties of uniformly hard languages
An arithmetical characterization of NP
Computational methods for database repair by signed formulae
Subtractive reductions and complete problems for counting complexity classes
Bounded query machines: on NP( ) and NPQUERY( )
The polynomial hierarchy and a simple model for competitive analysis
On quasilinear-time complexity theory
Complexity of Counting the Optimal Solutions
Optimization problems and the polynomial hierarchy
A low and a high hierarchy within NP
A refinement of the low and high hierarchies
A normal form for arithmetical representation of ${\mathcal N}{\mathcal P}$-sets
Hitting all maximal independent sets of a bipartite graph
Encoding deductive argumentation in quantified Boolean formulae
A uniform approach to obtain diagonal sets in complexity classes
Probabilistic complexity classes and lowness
Immunity and Simplicity for Exact Counting and Other Counting Classes
Coherence in finite argument systems.
Subclasses of Presburger arithmetic and the polynomial-time hierarchy
The complexity of problems for quantified constraints
Path-disruption games: bribery and a probabilistic model
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
On bounded query machines
Dominoes and the complexity of subclasses of logical theories
Linear connectivity problems in directed hypergraphs
On the acceptance power of regular languages
A second step toward the polynomial hierarchy
On the computational complexity of qualitative coalitional games
On polynomial time one-truth-table reducibility to a sparse set
Perfect correspondences between dot-depth and polynomial-time hierarchies
Complexity results for preference aggregation over ($m$)CP-nets: Pareto and majority voting
On the Containment Problem for Linear Sets
A System of Interaction and Structure III: The Complexity of BV and Pomset Logic
Relations among parallel and sequential computation models
Towards logical foundations for probabilistic computation
Nondeterministic stack register machines
Deterministic summation modulo $\mathcal B_{n}$, the semigroup of binary relations on $0,1, \dots, n-1$
Complexity results for preference aggregation over $(m)$CP-nets: max and rank voting
Computational complexity characterization of protecting elections from bribery
Improving Strategies via SMT Solving
The role of rudimentary relations in complexity theory
Characterising equilibrium logic and nested logic programs: Reductions and complexity,
Characterizing polynomial complexity classes by reducibilities
A note on sparse sets and the polynomial-time hierarchy
Dot operators
Complexity of the multilevel critical node problem
Bounding queries in the analytic polynomial-time hierarchy
UP and the low and high hierarchies: A relativized separation
The robustness of LWPP and WPP, with an application to graph reconstruction
On the synchronization of semi-traces
On the complexity of robust multi-stage problems with discrete recourse
Computation models and function algebras
Testing containment of object-oriented conjunctive queries is ∏2p-hard
Title not available (Why is that?)
On counting propositional logic and Wagner's hierarchy
A recursion-theoretic characterisation of the positive polynomial-time functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1241440)