The polynomial-time hierarchy

DOI10.1016/0304-3975(76)90061-XzbMATH Open0353.02024DBLPjournals/tcs/Stockmeyer76WikidataQ55954590 ScholiaQ55954590MaRDI QIDQ1236109FDOQ1236109

Authors: Larry J. Stockmeyer

Publication date: 1977

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Hierarchies of computability and definability (03D55) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

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

Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
Practical algorithms for MSO model-checking on tree-decomposable graphs
A complexity theory of constructible functions and sheaves
Belief revision and update: Complexity of model checking
Bilevel programming and the separation problem
The complexity of Boolean formula minimization
The difference and truth-table hierarchies for NP
Arithmetization: A new method in structural complexity theory
\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
The complexity of computing the permanent
Lower complexity bounds in justification logic
Graph properties checkable in linear time in the number of vertices
A restricted second order logic for finite structures
Efficient timed model checking for discrete-time systems
Algorithmic uses of the Feferman-Vaught theorem
Real addition and the polynomial hierarchy
Henkin quantifiers and complete problems
Complexity classes for self-assembling flexible tiles
Computational complexity of finite asynchronous cellular automata
Intuitionistic propositional logic is polynomial-space complete
The complexity of optimization problems
The computational complexity of asymptotic problems. I: Partial orders
Tree-width and the monadic quantifier hierarchy.
On problems without polynomial kernels
Space-bounded hierarchies and probabilistic computations
Random generation of combinatorial structures from a uniform distribution
A polynomial algorithm for deciding bisimilarity of normed context-free processes
On uniform circuit complexity
The complexity of two-player games of incomplete information
Domino-tiling games
Quantifier reordering for QBF
Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
Logical and schematic characterization of complexity classes
The minimum equivalent DNF problem and shortest implicants
Acceptance in incomplete argumentation frameworks
Lower bounds for multiplayer noncooperative games of incomplete information
On the representation and querying of sets of possible worlds
Complexity of counting the optimal solutions
The typed lambda-calculus is not elementary recursive
New developments in structural complexity theory
Methods for proving completeness via logical reductions
On the counting complexity of propositional circumscription
Complexity of near-optimal robust versions of multilevel optimization problems
Approximate counting, uniform generation and rapidly mixing Markov chains
An algorithm for direct construction of complete merged processes
Kernelization -- preprocessing with a guarantee
BDD-based decision procedures for the modal logic K ★
Characterizing parallel hierarchies by reducibilities
Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
Pseudorandom bits for constant depth circuits
Some consequences of non-uniform conditions on uniform classes
The complexity of query evaluation in indefinite temporal constraint databases
Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
Extensions of MSO and the monadic counting hierarchy
On the relative complexity of hard problems for complexity classes without complete problems
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
The complexity of combinatorial problems with succinct input representation
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
BPP and the polynomial hierarchy
Context-sensitive transitive closure operators
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Does co-NP have short interactive proofs ?
More complicated questions about maxima and minima, and some closures of NP
Parallel computation with threshold functions
Complexity of Boolean algebras
The strong exponential hierarchy collapses
Capturing complexity classes by fragments of second-order logic
Upper bounds on recognition of a hierarchy of non-context-free languages
Conformant plans and beyond: principles and complexity
Computational complexity of the discrete competitive facility location problem
Error-bounded probabilistic computations between MA and AM
Axiomatizing physical experiments as oracles to algorithms
On uniformity within \(NC^ 1\)
Fault-tolerance and complexity (extended abstract)
Boolean functions as models for quantified Boolean formulas
Logic, semigroups and automata on words
The computational complexity of multi-level linear programs
Lindström quantifiers and leaf language definability
Subtractive reductions and complete problems for counting complexity classes
The polynomial hierarchy and a simple model for competitive analysis
On quasilinear-time complexity theory
A low and a high hierarchy within NP
RelativizedNC
Graph isomorphism is in the low hierarchy
Motion planning with pulley, rope, and baskets
Line-based affine reasoning in Euclidean plane
Probabilistic complexity classes and lowness
A characterization of definability of second-order generalized quantifiers with applications to non-definability
Parity, circuits, and the polynomial-time hierarchy
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
The invariant problem for binary string structures and the parallel complexity theory of queries
Semantic query optimization in the presence of types
Universal quantifiers and time complexity of random access machines
Reductions on NP and p-selective sets
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
Displaying trees across two phylogenetic networks
On completeness for NP via projection translations
Model-checking hierarchical structures
Deciding safety properties in infinite-state pi-calculus via behavioural types
Results on communication complexity classes

This page was built for publication: The polynomial-time hierarchy

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