The polynomial-time hierarchy

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

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)

On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
Displaying trees across two phylogenetic networks
Lower complexity bounds in justification logic
On completeness for NP via projection translations
Algorithmic uses of the Feferman-Vaught theorem
Model-checking hierarchical structures
Deciding safety properties in infinite-state pi-calculus via behavioural types
Results on communication complexity classes
On adaptive DLOGTIME and POLYLOGTIME reductions
Pinpointing the complexity of the interval min-max regret knapsack problem
A remark on collective quantification
On quantified linear implications
On the Complexity of Inverse Mixed Integer Linear Optimization
Expressiveness and complexity of graph logic
A uniform method for proving lower bounds on the computational complexity of logical theories
Exotic quantifiers, complexity classes, and complete problems
Efficient Probabilistically Checkable Debates
Querying logical databases
On the expressive power of database queries with intermediate types
Number of quantifiers is better than number of tape cells
Logarithmic advice classes
On sparse hard sets for counting classes
Fine hierarchies and m-reducibilities in theoretical computer science
Succinctness as a source of complexity in logical formalisms
Henkin quantifiers and Boolean formulae: a certification perspective of DQBF
The most nonelementary theory
Toward credible belief base revision
On the complexity of queries in the logical data model
A complex analogue of Toda's theorem
An argument-based approach to reasoning with clinical knowledge
Games against nature
Counting classes: Thresholds, parity, mods, and fewness
\(\Sigma_ 2SPACE(n)\) is closed under complement
The complexity of online manipulation of sequential elections
The consequences of eliminating NP solutions
Verification in staged tile self-assembly
Model checking mobile ambients
On some natural complete operators
Simple characterizations of \(P(\# P)\) and complete problems
On hardness of one-way functions
On counting problems and the polynomial-time hierarchy
On the expressive power of monadic least fixed point logic
Locating \(P\)/poly optimally in the extended low hierarchy
Circuit lower bounds in bounded arithmetics
Second-order propositional modal logic and monadic alternation hierarchies
Weighted Boolean Formula Games
Complete sets and closeness to complexity classes
Boolean operations, joins, and the extended low hierarchy
Structure and complexity of relational queries
Strong nondeterministic polynomial-time reducibilities
Rudimentary relations and primitive recursion: A toolbox
Observations on complete sets between linear time and polynomial time
On the closure of certain function classes under integer division by polynomially-bounded functions
On the complexity of counting in the polynomial hierarchy
All superlinear inverse schemes are coNP-hard
Gap-definable counting classes
More on BPP and the polynomial-time hierarchy
An arithmetical characterization of NP
Separating classes in the exponential-time hierarchy from classes in PH
A note on parallel queries and the symmetric-difference hierarchy.
Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
Nonerasing, counting, and majority over the linear time hierarchy
Most frugal explanations in Bayesian networks
Preprocessing of intractable problems
On hiding information from an oracle
\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
On the definitions of some complexity classes of real numbers
Analyzing restricted fragments of the theory of linear arithmetic
The maximum value problem and NP real numbers
Complexity classes and theories of finite models
A complexity theory for feasible closure properties
The complexity of counting quantifiers on equality languages
Path-disruption games: bribery and a probabilistic model
A simple proof of a theorem of Statman
Conditional independence in propositional logic.
Linear connectivity problems in directed hypergraphs
Graph editing problems with extended regularity constraints
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
Graph properties checkable in linear time in the number of vertices
Fault-tolerance and complexity (Extended abstract)
A restricted second order logic for finite structures
Efficient timed model checking for discrete-time systems
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

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)