Premium
The polynomial hierarchy for some structures over the binary words
Author(s) -
Nübling Herwig
Publication year - 2007
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200610025
Subject(s) - hierarchy , mathematics , construct (python library) , polynomial , polynomial hierarchy , algebraic number , algebraic structure , binary number , combinatorics , discrete mathematics , pure mathematics , algebra over a field , time complexity , computer science , arithmetic , mathematical analysis , economics , market economy , programming language
For each k > 0 we construct an algebraic structure over which the polynomial hierarchy collapses at level k . We also find an algebraic structure over which the polynomial hierarchy does not collapse. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)