An arithmetical characterization of NP
From MaRDI portal
Publication:1171050
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
existential quantifiers; universal quantifiers; arithmetical representability; non- deterministic Turing machine; non-deterministic computability; quantifier prefix
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