NP-Complete Decision Problems for Quadratic Polynomials

In this article we show the NP-completeness of some simple number-theoretic problems. Natural simplifications of these problems invariably are known to be in P. Our research was motivated by the question whether one could study non-deterministic computation without loss of generality on a restricted, number theoretically significant class of nondeterministic Turing machines, the nondeterministic diophantine machines defined below [1,2]. The results suggest this is true.

Authors

• Kenneth L. Manders
• Leonard M. Adleman

Keywords

No keywords are indexed for this paper.