SeparatingPH fromPP by relativization

DOI10.1007/BF02582920MaRDI QIDQ4025322zbMATH OpenOpenAlexFDO

Authors Bin Fu

Publication date 18 February 1993

Published in Acta Mathematica Sinica, English Series (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

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

Cites work

• The complexity of combinatorial problems with succinct input representation

Cited in

(6)

• A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
• Perceptrons, PP, and the polynomial hierarchy
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Extremal properties of polynomial threshold functions
• On testing monomials in multivariate polynomials
• scientific article; zbMATH DE number 58312 (Why is no real title available?)

This page was built for publication: SeparatingPH fromPP by relativization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4025322)