SeparatingPH fromPP by relativization

DOI10.1007/BF02582920zbMATH Open0793.68077OpenAlexW2325700781MaRDI QIDQ4025322FDOQ4025322

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 (7)

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

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)