Nondeterministic polynomial-time computations and models of arithmetic

DOI10.1145/78935.78941zbMath0698.68046OpenAlexW1978337116MaRDI QIDQ3476273

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

NP-completenonstandard models of arithmeticcomplexity classesnondeterministic Turing machinecomputation by abstract devicesdiophantine sets

Mathematics Subject Classification ID

Related Items (4)

On the metamathematics of the P vs. NP question ⋮ \(\text{NP}\not={co}\)-NP and models of arithmetic ⋮ P, NP, Co-NP and weak systems of arithmetic ⋮ Construction of models of bounded arithmetic by restricted reduced powers

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