PP is as Hard as the Polynomial-Time Hierarchy
From MaRDI portal
Publication:3359758
DOI10.1137/0220053zbMath0733.68034OpenAlexW2137407595WikidataQ56386808 ScholiaQ56386808MaRDI QIDQ3359758
Publication date: 1991
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/67979ea92b2cba0e504a596a4c552de4047a39f8
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, Immunity and Simplicity for Exact Counting and Other Counting Classes, The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems, Algorithms and Complexity for Turaev-Viro Invariants, Counting Homomorphisms to Square-Free Graphs, Modulo 2, The Odds of Staying on Budget, Quantified Derandomization: How to Find Water in the Ocean, Nonuniform ACC Circuit Lower Bounds, Counting Small Induced Subgraphs Satisfying Monotone Properties, On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer, On closure properties of bounded two-sided error complexity classes, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, Unnamed Item, Exploiting Database Management Systems and Treewidth for Counting, On the computational complexity of the Dirichlet Problem for Poisson's Equation, On lower bounds of the closeness between complexity classes, Parameterized Derandomization, A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances, Parameterised counting in logspace, Commuting quantum circuits and complexity of Ising partition functions, The power of natural properties as oracles, Parameterised and fine-grained subgraph counting, modulo 2, Structural complexity of rational interactive proofs, Parameterized Counting and Cayley Graph Expanders, Unnamed Item, Unnamed Item, Unnamed Item, On the power of generalized Mod-classes, On the Power of Statistical Zero Knowledge, Percentile queries in multi-dimensional Markov decision processes, ON HIGHER ARTHUR-MERLIN CLASSES, Promise Problems on Probability Distributions, On Computing the Total Variation Distance of Hidden Markov Models., ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane, On pseudorandomness and resource-bounded measure, On Toda’s Theorem in Structural Communication Complexity, Unnamed Item, Unnamed Item, Unnamed Item, Hyper-polynomial hierarchies and the polynomial jump, On the parameterized complexity of approximate counting, Pure Nash equilibria in a generalization of congestion games allowing resource failures, Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On Existentially First-Order Definable Languages and Their Relation to NP, Relations and equivalences between circuit lower bounds and karp-lipton theorems, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials, The Complexity of Homomorphism Indistinguishability, Counting Answers to Existential Questions, Derandomizing Isolation in Space-Bounded Settings, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, Unnamed Item, Counting problems for parikh images, Computing Linear Extensions for Polynomial Posets Subject to Algebraic Constraints, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Unnamed Item, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, Counting Unlabelled Subtrees of a Tree is #P-complete, A note on SpanP functions, P Systems Simulating Oracle Computations, The fewest clues problem, The correlation between parity and quadratic polynomials mod \(3\), On closure properties of GapP, Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness], Dependence logic with a majority quantifier, Same-decision probability: a confidence measure for threshold-based decisions, Perceptrons, PP, and the polynomial hierarchy, On ACC, Completeness, approximability and exponential time results for counting problems with easy decision version, Circuit lower bounds from learning-theoretic approaches, Probabilistic causes in Markov chains, The landscape of communication complexity classes, Recursion theoretic characterizations of complexity classes of counting functions, On the complexity of finding shortest variable disjunction branch-and-bound proofs, Is Valiant-Vazirani's isolation probability improvable?, On the complexity of energy storage problems, The size of SPP, Uniform proofs of ACC representations, Average-case intractability vs. worst-case intractability, The effect of combination functions on the complexity of relational Bayesian networks, Parameterized circuit complexity and the \(W\) hierarchy, On the connection between interval size functions and path counting, The minimum oracle circuit size problem, Dual VP classes, Universally serializable computation, Processing succinct matrices and vectors, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, Pure Nash equilibria in a generalization of congestion games allowing resource failures, A dichotomy in the complexity of counting database repairs, An abstract model for branching and its application to mixed integer programming, Extensions of MSO and the monadic counting hierarchy, The complexity of the \(K\)th largest subset problem and related problems, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., The complexity of power indexes with graph restricted coalitions, Parameterized random complexity, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Most probable explanations in Bayesian networks: complexity and tractability, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Thirty years of credal networks: specification, algorithms and complexity, Lower bounds for the determinantal complexity of explicit low degree polynomials, On a theorem of Razborov, The complexity of Bayesian networks specified by propositional and relational languages, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, The complexity of problems for quantified constraints, A complex analogue of Toda's theorem, A structured view on weighted counting with relations to counting, quantum computation and applications, Some connections between bounded query classes and non-uniform complexity., Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, THE THOMPSON–HIGMAN MONOIDS Mk,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Lower bounds against weakly-uniform threshold circuits, On the acceptance power of regular languages, On quasilinear-time complexity theory, Modulo classes and logarithmic advice, Shallow laconic P-systems can count, Tree compression using string grammars, Acceptance in incomplete argumentation frameworks, Universal relations and {\#}P-completeness, A note on the permanent value problem, Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games, The equivalence of sampling and searching, Algorithms for modular counting of roots of multivariate polynomials, Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem, Graph isomorphism is low for PP, Quantum and classical complexity classes: Separations, collapses, and closure properties, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Leaf languages and string compression, The parameterized complexity of probability amplification, Computational complexity of stochastic programming problems, LWPP and WPP are not uniformly gap-definable, Competing provers yield improved Karp-Lipton collapse results, A complexity theory for hard enumeration problems, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, Structural properties of oracle classes, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, The complexity of power-index comparison, Efficient learning algorithms yield circuit lower bounds, A remark on collective quantification, From a zoo to a zoology: Towards a general theory of graph polynomials, Complexity results for probabilistic answer set programming, Definability for model counting, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Relating polynomial time to constant depth, The complexity of counting homomorphisms to cactus graphs modulo 2, A lower bound for monotone arithmetic circuits computing \(0-1\) permanent, Algorithms and complexity for Turaev-Viro invariants, Time-space tradeoffs for satisfiability, Circuits over PP and PL, The counting complexity of group-definable languages, Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\), A complexity theory of constructible functions and sheaves, Structural control in weighted voting games, Tally NP sets and easy census functions., On the probabilistic closure of the loose unambiguous hierarchy, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Randomness vs time: Derandomization under a uniform assumption, Gap-definable counting classes, PSPACE is provable by two provers in one round
