Nondeterministic polynomial-time computations and models of arithmetic

DOI10.1145/78935.78941MaRDI QIDQ3476273zbMATH OpenOpenAlexFDO

Authors Attila Máté

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/78935.78941

zbMATH Keywords

complexity classesNP-completenonstandard models of arithmeticnondeterministic Turing machinecomputation by abstract devicesdiophantine sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Nonstandard models of arithmetic (03H15)

Recommendations

• On Models of a Nondeterministic Computation
• Publication:3487327
• scientific article; zbMATH DE number 4139739
• Shorter arithmetization of nondeterministic computations
• scientific article; zbMATH DE number 4051602
• Arithmetic theories for computational complexity problems
• scientific article; zbMATH DE number 4024793
• scientific article; zbMATH DE number 1303206
• Polynomial time computations in models of ET
• scientific article; zbMATH DE number 3859101

Cited in

(10)

• scientific article; zbMATH DE number 922619 (Why is no real title available?)
• scientific article; zbMATH DE number 1993590 (Why is no real title available?)
• scientific article; zbMATH DE number 4090803 (Why is no real title available?)
• On the metamathematics of the P vs. NP question
• Polynomial-time versus recursive models
• Polynomial time computations in models of ET
• Construction of models of bounded arithmetic by restricted reduced powers
• An approximation approach to Cook hypothesis
• \(\text{NP}\not={co}\)-NP and models of arithmetic
• P, NP, Co-NP and weak systems of arithmetic

This page was built for publication: Nondeterministic polynomial-time computations and models of arithmetic

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