NP-Complete decision problems for binary quadratics

摘要

The computational complexity of deciding whether a polynomial with integer coefficients has natural-number zeros ranges from deterministic polynomial time feasibility (for polynomials in one variable or of degree one) to undecidability (presently known to hold for polynomials in nine or more variables). We show that for the two-variable quadratics of the form αx2 + βy − γ = 0; α, β, γ ϵ ω, the problem is NP-complete. This implies NP-completeness of certain questions about the solutions x of x2 = α modulo β; α, β, ξ ϵ ω. It also shows that a nondeterministic Turing machine restricted to evaluating deterministically polynomials of a given form at nondeterministically constructed argument values (called a nondeterministic Diophantine machine below) can solve an NP-complete problem in polynomial time.