Abstract. An analysis of the unsolvability of Diophantine equations showed that problems of recognition of properties of the NP class are solvable, i.e., a non-deterministic algorithm or exhaustive search at the input of the problem gives a positive or negative answer. For polynomial Diophantine equations, such a non-deterministic algorithm does not exist. A simple version of Gоdel’s theorem on the incompleteness of arithmetic follows from the unsolvability of Diophantine equations.

Keywords: NP-complete problems, Diophantine equations, non-deterministic algorithm.