SeparatingPH fromPP by relativization

DOI10.1007/BF02582920zbMath0793.68077OpenAlexW2325700781MaRDI QIDQ4025322

Bin Fu

Publication date: 18 February 1993

Published in: Acta Mathematica Sinica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02582920

zbMATH Keywords

polynomial time hierarchypolynomial time probabilistic complexity class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ On testing monomials in multivariate polynomials ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ Extremal properties of polynomial threshold functions ⋮ A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy

Cites Work

• The complexity of combinatorial problems with succinct input representation

This page was built for publication: SeparatingPH fromPP by relativization