A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
type: Item
instance of: scholarly article
title: A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
zbMATH Open document ID: 0535.03016
DOI: 10.1016/0022-0000(83)90048-X
author: Bernard Hodgson
author: Clement F. Kent
published in: Journal of Computer and System Sciences
publication date: 1983-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 3849209
zbMATH Keywords: polynomial-time hierarchy
zbMATH Keywords: diophantine hierarchy
zbMATH Keywords: polynomial matrix hierarchy
MaRDI profile type: Publication
cites work: Q4138187
cites work: Arithmetical problems and recursively enumerable predicates
cites work: Q3247126
cites work: Hilbert's Tenth Problem is Unsolvable
cites work: Q4115143
cites work: Q3937379
cites work: Q4142699
cites work: An arithmetical characterization of NP
cites work: NP-complete decision problems for binary quadratics
cites work: A new proof of the theorem on exponential diophantine representation of enumerable sets
cites work: Arithmetical representation of recursively enumerable sets
cites work: Complete sets and the polynomial-time hierarchy
Recommended article: A remark on arithmetic equivalence and the normset
Recommended article: A normal form for arithmetical derivations implying the \(\omega\)-consistency of arithmetic
Recommended article: Representing hyper-arithmetical sets by equations over sets of integers
Recommended article: Normal Forms for Characteristic Functions on n-ary Relations
Recommended article: PRENEX NORMAL FORM THEOREMS IN SEMI-CLASSICAL ARITHMETIC
Recommended article: Q3153291
Recommended article: On \(n\)-normal posets
Recommended article: Arithmetic progressions in the solution sets of norm form equations
Recommended article: Normal forms for representations of representation-finite algebras
Recommended article: Q4831483
description: scientific article; zbMATH DE number 3849209