The polynomial hierarchy for some structures over the binary words

DOI10.1002/MALQ.200610025MaRDI QIDQ3423149zbMATH OpenOpenAlexFDO

Authors Herwig Nübling

Publication date 20 February 2007

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200610025

zbMATH Keywords

BSS-modelpolynomial hierarchy

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3871339
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• Relativized polynomial hierarchies extending two levels
• The polynomial-time hierarchy and sparse oracles

Cited in

(4)

• \(\mathbf P =\mathbf{NP}\) for some structures over the binary words
• Separations and transfers in the polynomial hierarchy of infinite abelian groups
• Hyper-polynomial hierarchies and the polynomial jump
• Polynomial versus exponential growth in repetition-free binary words

This page was built for publication: The polynomial hierarchy for some structures over the binary words

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