scientific article

DOI10.2307/2273938zbMath0592.03027OpenAlexW4244516892MaRDI QIDQ3720579

Bruno Poizat

Publication date: 1986

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2273938

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algorithmspolynomial hierarchyoracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)

Related Items (6)

Random oracles separate PSPACE from the polynomial-time hierarchy ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ Forcing complexity: Minimum sizes of forcing conditions. ⋮ Generic oracles, uniform machines, and codes ⋮ Degrees of Dowd-type generic oracles ⋮ Complexity of the \(r\)-query tautologies in the presence of a generic oracle

Cites Work

• The polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Etude D'Un Forcing en Théorie des Modèles

This page was built for publication: