Nonlinear algebra and optimization on rings are “hard”. (English) Zbl 0686.68037

Hunt, H. B. III; Stearns, R. E.

SIAM J. Comput. 16, 910-929 (1987).

The paper shows for many problems concerning solutions of systems of algebraic equations and nonlinear optimizations on rings that they are NP-, co-NP, or #P-hard. The most important results are:
1. Deciding whether a system of quadratic equations has a solution is NP- hard on rings which either have an idempotent element or no zero- divisors, so in particular over integers, rationals, reals, or complex numbers.
2. Minimizing or maximizing a linear function subject to quadratic constraints on rings with multiplicative identity and a linear order is both NP- and co-NP-hard.
3. Deciding whether a quadratic multivariate polynomial with integer coefficients over the reals has \(\{\) 0,1\(\}\)-valued roots is NP-complete.

Reviewer: H.Alt

MSC:

68Q25	Analysis of algorithms and problem complexity
68W30	Symbolic computation and algebraic computation
13A99	General commutative ring theory
16Y99	Generalizations

Keywords:

NP-completeness; algebraic computation; computational complexity; nonlinear optimizations