An arithmetical characterization of NP

DOI10.1016/0304-3975(82)90076-7zbMath0498.03023OpenAlexW2018323941MaRDI 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 quantifiersuniversal quantifiersarithmetical representabilitynon- deterministic Turing machinenon-deterministic computabilityquantifier prefix

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

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, Circuit lower bounds in bounded arithmetics, Arithmetizing uniform \(NC\), \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly, \(\text{NP}\not={co}\)-NP and models of arithmetic, Metafinite model theory, A theory for Log-Space and NLIN versus co-NLIN, Multifunction algebras and the provability of \(PH\downarrow\), A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets, Polynomial time computations in models of ET

Cites Work

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