An arithmetical characterization of NP

DOI10.1016/0304-3975(82)90076-7zbMath0498.03023MaRDI QIDQ1171050

Bernard R. Hodgson, Clement F. Kent

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90076-7

zbMATH Keywords

existential quantifiers; universal quantifiers; arithmetical representability; non- deterministic Turing machine; non-deterministic computability; quantifier prefix

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

03D25: Recursively (computably) enumerable sets and degrees

Related Items

A theory for Log-Space and NLIN versus co-NLIN, Metafinite model theory, Circuit lower bounds in bounded arithmetics, \(\text{NP}\not={co}\)-NP and models of arithmetic, A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets, Polynomial time computations in models of ET, \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly, Uniform normal form for general time-bounded complexity classes, Arithmetizing uniform \(NC\), Recursion theoretic characterizations of complexity classes of counting functions, Metafinite model theory, Multifunction algebras and the provability of \(PH\downarrow\), Arithmetical definability and computational complexity

Cites Work

• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The bounded arithmetic hierarchy
• On the Product of the Primes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item