A normal form for arithmetical representation of N P-sets

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

Authors Bernard 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)

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

• 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?)
• 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
• NP-complete decision problems for binary quadratics

Cited in

(7)

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