The polynomial-time hierarchy

From MaRDI portal

Publication:1236109

Jump to:navigation, search

DOI10.1016/0304-3975(76)90061-XzbMath0353.02024WikidataQ55954590 ScholiaQ55954590MaRDI QIDQ1236109

Larry J. Stockmeyer

Publication date: 1977

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

Mathematics Subject Classification ID

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

Related Items

Random generation of combinatorial structures from a uniform distribution, Robust approach to restricted items selection problem, Quantifier reordering for QBF, On bounded query machines, Continuous optimization problems and a polynomial hierarchy of real functions, Uniform normal form for general time-bounded complexity classes, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP, Henkin quantifiers and complete problems, Complexity of counting the optimal solutions, The complexity of combinatorial problems with succinct input representation, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, A note on complete problems for complexity classes, Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games, On the complexity of kings, On hardness of one-way functions, Some observations on the connection between counting and recursion, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, The complexity of optimization problems, Parallel computation with threshold functions, More complicated questions about maxima and minima, and some closures of NP, Does co-NP have short interactive proofs ?, \(\Sigma_ 2SPACE(n)\) is closed under complement, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Promise problems complete for complexity classes, On the relative complexity of hard problems for complexity classes without complete problems, Probabilistic quantifiers and games, Completeness results for conflict-free vector replacement systems, Expressiveness and complexity of graph logic, Graph properties checkable in linear time in the number of vertices, The most nonelementary theory, Algorithmic uses of the Feferman-Vaught theorem, The complexity of computing the permanent, The complexity of computing minimal unidirectional covering sets, Autoreducibility, mitoticity, and immunity, Motion planning with pulley, rope, and baskets, Semantic query optimization in the presence of types, Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, Extensions of MSO and the monadic counting hierarchy, Bilevel programming and the separation problem, The complexity of Boolean formula minimization, Lower complexity bounds in justification logic, Model-checking hierarchical structures, Observations on complete sets between linear time and polynomial time, Deciding safety properties in infinite-state pi-calculus via behavioural types, Pinpointing the complexity of the interval min-max regret knapsack problem, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], New developments in structural complexity theory, Lower bounds for constant-depth circuits in the presence of help bits, A uniform method for proving lower bounds on the computational complexity of logical theories, A complex analogue of Toda's theorem, On the complexity of ranking, The consequences of eliminating NP solutions, Second-order propositional modal logic and monadic alternation hierarchies, Circuit lower bounds in bounded arithmetics, Practical algorithms for MSO model-checking on tree-decomposable graphs, Verification in incomplete argumentation frameworks, On adaptive DLOGTIME and POLYLOGTIME reductions, On the acceptance power of regular languages, On quasilinear-time complexity theory, A note on P-selective sets and closeness, Fine hierarchies and m-reducibilities in theoretical computer science, Analyzing restricted fragments of the theory of linear arithmetic, The complexity of counting quantifiers on equality languages, Computational complexity of finite asynchronous cellular automata, Methods for proving completeness via logical reductions, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Path-disruption games: bribery and a probabilistic model, Three \(\sum^ P_ 2\)-complete problems in computational learning theory, Arithmetization: A new method in structural complexity theory, On the complexity of queries in the logical data model, Graph editing problems with extended regularity constraints, On the counting complexity of propositional circumscription, Conformant plans and beyond: principles and complexity, Querying logical databases, The strong exponential hierarchy collapses, An argument-based approach to reasoning with clinical knowledge, Complexity classes for self-assembling flexible tiles, A remark on collective quantification, The complexity of almost linear diophantine problems, Exotic quantifiers, complexity classes, and complete problems, Linear connectivity problems in directed hypergraphs, On problems without polynomial kernels, BPP and the polynomial hierarchy, A low and a high hierarchy within NP, Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories, Strong nondeterministic polynomial-time reducibilities, Some consequences of non-uniform conditions on uniform classes, Complex Boolean networks obtained by diagonalization, The complexity of two-player games of incomplete information, On small generators, Space-bounded hierarchies and probabilistic computations, Real addition and the polynomial hierarchy, On some natural complete operators, On the complexity of counting in the polynomial hierarchy, Pseudorandom bits for constant depth circuits, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes, Simple sentences that are hard to decide, Games against nature, Lower bound results on lengths of second-order formulas, On the expressive power of monadic least fixed point logic, Expressiveness of Logic Programs under the General Stable Model Semantics, Universal quantifiers and time complexity of random access machines, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, Immunity and Simplicity for Exact Counting and Other Counting Classes, Relativization of Gurevich’s Conjectures, The polynomial hierarchy and a simple model for competitive analysis, On the synchronization of semi-traces, On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP, Computational tameness of classical non-causal models, On completeness for NP via projection translations, Structural analysis of polynomial-time query learnability, Definability in the class of all -frames – computability and complexity, RelativizedNC, Type 2 polynomial hierarchies, Reachability in Simple Neural Networks, Alternating (in)dependence-friendly logic, Taming strategy logic: non-recurrent fragments, The notion of abstraction in ontology-based data management, Intersection suffices for Boolean hierarchy equivalence, Toward credible belief base revision, On counting propositional logic and Wagner's hierarchy, Functional synthesis via input-output separation, Beyond NP: Quantifying over Answer Sets, Capturing the polynomial hierarchy by second-order revised Krom logic, Fixed points and attractors of reactantless and inhibitorless reaction systems, On the complexity of robust multi-stage problems with discrete recourse, The join can lower complexity, Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty, Rejection-proof mechanisms for multi-agent kidney exchange, The difference and truth-table hierarchies for NP, Unnamed Item, The Complexity Landscape of Outcome Determination in Judgment Aggregation, Fault-tolerance and complexity (Extended abstract), ANALYZING VULNERABILITIES OF CRITICAL INFRASTRUCTURES USING FLOWS AND CRITICAL VERTICES IN AND/OR GRAPHS, Computing on structures, On the cutting edge of relativization: The resource bounded injury method, On deciding some equivalences for concurrent processes, UP and the low and high hierarchies: A relativized separation, First-Order Model-Checking in Random Graphs and Complex Networks, Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata, A second step toward the strong polynomial-time hierarchy, On the Computational Complexity of Non-Dictatorial Aggregation, A restricted second order logic for finite structures, Complexity and expressive power of second‐order extended Horn logic, Counting classes: Thresholds, parity, mods, and fewness, Expressibility of Higher Order Logics, The Descriptive Complexity of the Deterministic Exponential Time Hierarchy, Belief revision and update: Complexity of model checking, Lower bounds for multiplayer noncooperative games of incomplete information, UP and the low and high hierarchies: A relativized separation, Hyper-polynomial hierarchies and the polynomial jump, Unnamed Item, Complexity aspects of a semi-infinite optimization problem†, Unnamed Item, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), On sets bounded truth-table reducible to $P$-selective sets, Answer Set Programming: A Primer, Unnamed Item, BDD-based decision procedures for the modal logic K ★, Complete sets and closeness to complexity classes, LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, The Relational Polynomial-Time Hierarchy and Second-Order Logic, On the Complexity of Inverse Mixed Integer Linear Optimization, Complexity classes and theories of finite models, A Unified Framework for Multistage Mixed Integer Linear Optimization, Computational complexity of the discrete competitive facility location problem, Pure Nash Equilibria in Resource Graph Games, On Quantifying Literals in Boolean Logic and its Applications to Explainable AI, A note on complete sets and transitive closure, Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions, Simple characterizations of \(P(\# P)\) and complete problems, On the complexity of computing the diameter of a polytope, On closure properties of GapP, Locating \(P\)/poly optimally in the extended low hierarchy, A polynomial algorithm for deciding bisimilarity of normed context-free processes, More on BPP and the polynomial-time hierarchy, The complexity and generality of learning answer set programs, Complexity of Presburger arithmetic with fixed quantifier dimension, Deciding a class of path formulas for conflict-free Petri nets, Separating classes in the exponential-time hierarchy from classes in PH, Index sets and presentations of complexity classes, The complexity of query evaluation in indefinite temporal constraint databases, Simplicity, immunity, relativizations and nondeterminism, Subclasses of Presburger arithmetic and the polynomial-time hierarchy, Dominoes and the complexity of subclasses of logical theories, The computational complexity of asymptotic problems. I: Partial orders, How to define a linear order on finite models, Graph isomorphism is in the low hierarchy, Approximate counting, uniform generation and rapidly mixing Markov chains, With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\), Descriptive characterizations of computational complexity, Rudimentary relations and primitive recursion: A toolbox, On the power of alternation on reversal-bounded alternating Turing machines with a restriction, 0-1 laws by preservation, An abstract model for branching and its application to mixed integer programming, On reachability equivalence for BPP-nets, Complexity of Boolean algebras, Query containment for data integration systems, A polynomial space construction of tree-like models for logics with local chains of modal connectives, Tree-width and the monadic quantifier hierarchy., A descriptive complexity approach to the linear hierarchy., Optimization problems and the polynomial hierarchy, On uniform circuit complexity, On time-space classes and their relation to the theory of real addition, A second-order system for polytime reasoning based on Grädel's theorem., Bounded query machines: on NP( ) and NPQUERY( ), The maximum value problem and NP real numbers, Some observations on the probabilistic algorithms and NP-hard problems, Recursion-theoretic ranking and compression, A uniform approach to obtain diagonal sets in complexity classes, Number of quantifiers is better than number of tape cells, A note on sparse oracles for NP, Reductions on NP and p-selective sets, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, Some connections between bounded query classes and non-uniform complexity., An arithmetical characterization of NP, On counting problems and the polynomial-time hierarchy, On the representation and querying of sets of possible worlds, On sets polynomially enumerable by iteration, On the expressive power of database queries with intermediate types, Strong and robustly strong polynomial-time reducibilities to sparse sets, Semigroup automaton structure by homomorphism and domain partition, Characterizing parallel hierarchies by reducibilities, The computational complexity of multi-level linear programs, Restricted relativizations of probabilistic polynomial time, Results on communication complexity classes, The descriptive complexity of decision problems through logics with relational fixed-point and capturing results, The invariant problem for binary string structures and the parallel complexity theory of queries, Capturing complexity classes by fragments of second-order logic, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Generalizations of Opt P to the polynomial hierarchy, Upper bounds on recognition of a hierarchy of non-context-free languages, Logarithmic advice classes, A note on the permanent value problem, Polynomial-time compression, A simple proof of a theorem of Statman, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets, On the closure of certain function classes under integer division by polynomially-bounded functions, Normal and sinkless Petri nets, On sparse hard sets for counting classes, Generalizations of matched CNF formulas, On deciding subsumption problems, Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy, On languages specified by relative acceptance, A second step toward the polynomial hierarchy, Intuitionistic propositional logic is polynomial-space complete, The typed lambda-calculus is not elementary recursive, Reasoning about strings in databases, On hiding information from an oracle, A note on sparse sets and the polynomial-time hierarchy, Probabilistic complexity classes and lowness, Definability, decidability, complexity, Logic, semigroups and automata on words, A restricted second order logic for finite structures, Expressive power and complexity of partial models for disjunctive deductive databases, Bounding queries in the analytic polynomial-time hierarchy, Relating polynomial time to constant depth, Boolean operations, joins, and the extended low hierarchy, Sentences over integral domains and their computational complexities, The closure of monadic NP, Succinctness as a source of complexity in logical formalisms, On deciding trace equivalences for processes, Hereditarily-finite sets, data bases and polynomial-time computability, Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\), The minimum equivalent DNF problem and shortest implicants, Gap-definable counting classes, Context-sensitive transitive closure operators, Logical and schematic characterization of complexity classes, The complexity of online bribery in sequential elections, Advanced algorithms for abstract dialectical frameworks based on complexity analysis of subclasses and SAT solving, Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic, A complexity theory for feasible closure properties, Efficient timed model checking for discrete-time systems, Computing queries with higher-order logics, Model checking mobile ambients, Arithmetical definability and computational complexity, Line-based affine reasoning in Euclidean plane, Non-essential arcs in phylogenetic networks, Complexity of question/answer games, Kernelization – Preprocessing with a Guarantee, Complexity of nonemptiness in control argumentation frameworks, Semantic Restrictions over Second-Order Logic, Characterising equilibrium logic and nested logic programs: Reductions and complexity,, The complexity of online manipulation of sequential elections, Query-monotonic Turing reductions, Relativized counting classes: Relations among thresholds, parity, and mods, Arity and alternation: a proper hierarchy in higher order logics, On uniformity within \(NC^ 1\), A tetrachotomy of ontology-mediated queries with a covering axiom, Weighted Boolean Formula Games, Boolean functions as models for quantified Boolean formulas, On the longest circuit in an alterable digraph, Parameterized complexity classes beyond para-NP, Verification in staged tile self-assembly, The rise and fall of semantic rule updates based onSE-models, A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, A note on \(\Sigma_2^p\)-completeness of a robust binary linear program with binary uncertainty set, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Descriptive complexity of deterministic polylogarithmic time and space, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Axiomatizing physical experiments as oracles to algorithms, Propositional truth maintenance systems: Classification and complexity analysis, Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting, Characterizing polynomial complexity classes by reducibilities, Extensions of an idea of McNaughton, Multistage robust discrete optimization via quantified integer programming, Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy, On the Complexity of Master Problems, The complexity of comparing optimal solutions, Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete, SO F : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy, Fair and efficient allocation with few agent types, few item types, or small value levels, Fixpoint logics over hierarchical structures, Deciding the word problem in pure double Boolean algebras, Henkin quantifiers and Boolean formulae: a certification perspective of DQBF, From NP-completeness to DP-completeness: a membrane computing perspective, From QBFs to \textsf{MALL} and back via focussing, Partial fixed point for finite models in second order logic, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, The complexity of problems for quantified constraints, A hierarchy of local decision, Display sets of normal and tree-child networks, Perfect correspondences between dot-depth and polynomial-time hierarchies, A characterization of definability of second-order generalized quantifiers with applications to non-definability, Complexity of near-optimal robust versions of multilevel optimization problems, Improving Strategies via SMT Solving, Acceptance in incomplete argumentation frameworks, On the definitions of some complexity classes of real numbers, An Algorithm for Direct Construction of Complete Merged Processes, Parity, circuits, and the polynomial-time hierarchy, On quantified linear implications, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Generating hard instances for robust combinatorial optimization, The role of rudimentary relations in complexity theory, \(\text{BTL}_{2}\) and the expressive power of \(\text{ECTL}^{+}\), The complexity of verifying population protocols, Error-bounded probabilistic computations between MA and AM, The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws, Subroutines in P systems and closure properties of their complexity classes, Most frugal explanations in Bayesian networks, Natural strategic ability, The trouble with the second quantifier, Complexity results for probabilistic answer set programming, Efficient Probabilistically Checkable Debates, The complexity of finding temporal separators under waiting time constraints, On the complexity of robust bilevel optimization with uncertain follower's objective, Domino-tiling games, Relativizing relativized computations, Borda-induced hedonic games with friends, enemies, and neutral players, Complexity bounds for the controllability of temporal networks with conditions, disjunctions, and uncertainty, Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting, Structure and complexity of relational queries, Subtractive reductions and complete problems for counting complexity classes, Displaying trees across two phylogenetic networks, Models of replacement schemes, All superlinear inverse schemes are coNP-hard, Resource bounded immunity and simplicity, A complexity theory of constructible functions and sheaves, A framework for generalized Benders' decomposition and its application to multilevel optimization, Conditional independence in propositional logic., Tally NP sets and easy census functions., Nonerasing, counting, and majority over the linear time hierarchy, Preprocessing of intractable problems, A note on parallel queries and the symmetric-difference hierarchy., On the restricted equivalence for subclasses of propositional logic, Limiting characterizations of low level space complexity classes, Hitting all maximal independent sets of a bipartite graph, On the Containment Problem for Linear Sets

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1236109&oldid=13316913"