Nondeterministic polynomial-time computations and models of arithmetic (Q3476273)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Nondeterministic polynomial-time computations and models of arithmetic |
scientific article |
Statements
Nondeterministic polynomial-time computations and models of arithmetic (English)
0 references
1990
0 references
computation by abstract devices
0 references
complexity classes
0 references
nondeterministic Turing machine
0 references
NP-complete
0 references
nonstandard models of arithmetic
0 references
diophantine sets
0 references
