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

DOI10.1016/0022-0000(83)90048-XzbMath0535.03016MaRDI QIDQ790804

Bernard R. Hodgson, Clement F. Kent

Publication date: 1983

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

zbMATH Keywords

polynomial-time hierarchydiophantine hierarchypolynomial matrix hierarchy

Mathematics Subject Classification ID

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

Related Items (5)

Uniform normal form for general time-bounded complexity classes ⋮ Arithmetical definability and computational complexity ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ Metafinite model theory ⋮ Metafinite model theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new proof of the theorem on exponential diophantine representation of enumerable sets
• An arithmetical characterization of NP
• Complete sets and the polynomial-time hierarchy
• NP-complete decision problems for binary quadratics
• Arithmetical representation of recursively enumerable sets
• Hilbert's Tenth Problem is Unsolvable
• Arithmetical problems and recursively enumerable predicates

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