An arithmetical characterization of NP

DOI10.1016/0304-3975(82)90076-7MaRDI QIDQ1171050zbMATH OpenOpenAlexFDO

Authors Clement F. Kent, Bernard Hodgson

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

arithmetical representabilityexistential quantifiersnon- deterministic Turing machinenon-deterministic computabilityquantifier prefixuniversal quantifiers

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)

Cites work

• Complete sets and the polynomial-time hierarchy
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• On the Product of the Primes
• The bounded arithmetic hierarchy
• The polynomial-time hierarchy

Cited in

(14)

• 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
• Arithmetical definability and computational complexity
• A theory for Log-Space and NLIN versus co-NLIN
• Circuit lower bounds in bounded arithmetics
• Metafinite model theory
• \(\text{NP}\not={co}\)-NP and models of arithmetic
• Bounded Henkin quantifiers and the exponential time hierarchy
• 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

This page was built for publication: An arithmetical characterization of NP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1171050)