A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets (Q790804)

In a previous paper [Theor. Comput. Sci. 21, 255-267 (1982; Zbl 0498.03023)] the same authors have obtained an arithmetical characterization of the class \({\mathcal N}{\mathcal P}\) in terms of ''exponential existential bounded arithmetical predicates''. Here, this result is strengthened, i.e. it is proved that all but one of the bounded universal quantifiers can be eliminated. As an interesting consequence, we note a relation between the polynomial-time hierarchy [\textit{L. J. Stockmeyer}, Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024); \textit{C. Wrathal}, ibid. 3, 23-33 (1977; Zbl 0366.02031)] and the diophantine-hierarchy [\textit{L. Adleman} and \textit{K. Manders}, Diophantine complexity, Proc. 17th Ann. Symp. Found. Comput. Sci., 81-88 (1976)]. This relation is obtained via a new hierarchy - the polynomial matrix hierarchy - introduced in the paper under review.