A normal form for arithmetical representation of N P-sets

摘要

It is shown that in the arithmetical characterization of the class N P previously given by the authors (Theoret. Comput. Sci. 21 (1982), 255–267), called EEBA form, all but one of the bounded universal quantifiers can be eliminated. This shows that EEBA sets do not form a hierarchy with respect to quantifier alternation. An application of the main result yields a transformation of the Polynomial Time Hierarchy of Meyer and Stockmeyer into the Diophantine Hierarchy of Adleman and Manders.