SeparatingPH fromPP by relativization
From MaRDI portal
Publication:4025322
DOI10.1007/BF02582920zbMath0793.68077MaRDI QIDQ4025322
Publication date: 18 February 1993
Published in: Acta Mathematica Sinica (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy, Perceptrons, PP, and the polynomial hierarchy
Cites Work