A normal form for arithmetical representation of N P-sets

DOI10.1016/0022-0000(83)90048-XMaRDI QIDQ790804zbMATH OpenFDO

Authors Bernard Hodgson, Clement F. Kent

Publication date 1983

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(83)90048-X

zbMATH Keywords

diophantine hierarchypolynomial matrix hierarchypolynomial-time hierarchy

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Review text

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.

Recommendations

• A remark on arithmetic equivalence and the normset
• A normal form for arithmetical derivations implying the \(\omega\)-consistency of arithmetic
• Representing hyper-arithmetical sets by equations over sets of integers
• Normal Forms for Characteristic Functions on n-ary Relations
• Prenex normal form theorems in semi-classical arithmetic
• scientific article
• On \(n\)-normal posets
• Arithmetic progressions in the solution sets of norm form equations
• Normal forms for representations of representation-finite algebras
• scientific article; zbMATH DE number 2124085

Cites work

• A new proof of the theorem on exponential diophantine representation of enumerable sets
• An arithmetical characterization of NP
• Arithmetical problems and recursively enumerable predicates
• Arithmetical representation of recursively enumerable sets
• Complete sets and the polynomial-time hierarchy
• Hilbert's Tenth Problem is Unsolvable
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3754672 (Why is no real title available?)
• scientific article; zbMATH DE number 3539209 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• NP-complete decision problems for binary quadratics

Cited in

(7)

• Uniform normal form for general time-bounded complexity classes
• Recursion theoretic characterizations of complexity classes of counting functions
• Metafinite model theory
• Arithmetical definability and computational complexity
• Diophantine hierarchy
• scientific article; zbMATH DE number 3904571 (Why is no real title available?)
• Metafinite model theory

This page was built for publication: A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets

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