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

existential quantifiersuniversal quantifiersarithmetical representabilitynon- deterministic Turing machinenon-deterministic computabilityquantifier prefix

Mathematics Subject Classification ID

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

Cites work

• 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?)
• Complete sets and the polynomial-time hierarchy
• On the Product of the Primes
• The bounded arithmetic hierarchy
• The polynomial-time hierarchy

Cited in

(14)

• Arithmetizing uniform NC
• Uniform normal form for general time-bounded complexity classes
• Metafinite model theory
• Multifunction algebras and the provability of PH
• Recursion theoretic characterizations of complexity classes of counting functions
• A theory for Log-Space and NLIN versus co-NLIN
• Arithmetical definability and computational complexity
• Circuit lower bounds in bounded arithmetics
• Metafinite model theory
• 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
• \(\text{NP}\not={co}\)-NP and models of arithmetic

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)