Pages that link to "Item:Q3359758"
From MaRDI portal
The following pages link to PP is as Hard as the Polynomial-Time Hierarchy (Q3359758):
Displaying 50 items.
- The complexity of counting homomorphisms to cactus graphs modulo 2 (Q2828223) (← links)
- P Systems Simulating Oracle Computations (Q2890301) (← links)
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← links)
- Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$ (Q2969880) (← links)
- THE THOMPSON–HIGMAN MONOIDS M<sub>k,i</sub>: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY (Q2996837) (← links)
- A simple proof of Toda's theorem (Q3002806) (← links)
- Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth (Q3012845) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Promise Problems on Probability Distributions (Q3297824) (← links)
- Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials (Q3392951) (← links)
- The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems (Q3448788) (← links)
- Algorithms and Complexity for Turaev-Viro Invariants (Q3448792) (← links)
- Counting Homomorphisms to Square-Free Graphs, Modulo 2 (Q3448822) (← links)
- The Odds of Staying on Budget (Q3449479) (← links)
- Parameterized Derandomization (Q3503586) (← links)
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances (Q3503590) (← links)
- On Toda’s Theorem in Structural Communication Complexity (Q3599108) (← links)
- Counting hierarchies: Polynomial time and constant depth circuits (Q3971277) (← links)
- On lower bounds of the closeness between complexity classes (Q4032931) (← links)
- Immunity and Simplicity for Exact Counting and Other Counting Classes (Q4265536) (← links)
- Counting Unlabelled Subtrees of a Tree is #P-complete (Q4504966) (← links)
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS (Q4528761) (← links)
- On the computational complexity of the Dirichlet Problem for Poisson's Equation (Q4593239) (← links)
- On Existentially First-Order Definable Languages and Their Relation to NP (Q4718893) (← links)
- On closure properties of bounded two-sided error complexity classes (Q4835865) (← links)
- On the power of generalized Mod-classes (Q4864444) (← links)
- On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane (Q4918034) (← links)
- Simple doubly-efficient interactive proof systems for locally-characterizable sets (Q4993281) (← links)
- Computing Linear Extensions for Polynomial Posets Subject to Algebraic Constraints (Q5001675) (← links)
- On Computing the Total Variation Distance of Hidden Markov Models. (Q5002817) (← links)
- (Q5005151) (← links)
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2) (Q5005160) (← links)
- (Q5005182) (← links)
- Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2 (Q5013574) (← links)
- Quantified Derandomization: How to Find Water in the Ocean (Q5060673) (← links)
- Counting Small Induced Subgraphs Satisfying Monotone Properties (Q5071087) (← links)
- On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer (Q5080487) (← links)
- (Q5090385) (← links)
- (Q5091154) (← links)
- Counting Answers to Existential Questions (Q5091275) (← links)
- Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782) (← links)
- (Q5092385) (← links)
- The Complexity of Homomorphism Indistinguishability (Q5092416) (← links)
- Counting problems for parikh images (Q5111226) (← links)
- (Q5111868) (← links)
- On the Power of Statistical Zero Knowledge (Q5117376) (← links)
- (Q5121894) (← links)
- (Q5121895) (← links)
- (Q5121907) (← links)
- (Q5121909) (← links)
