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

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

Cites work

• The complexity of combinatorial problems with succinct input representation

Cited in

(6)

• Perceptrons, PP, and the polynomial hierarchy
• On testing monomials in multivariate polynomials
• A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
• Extremal properties of polynomial threshold functions
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• 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)