zbMATH — the first resource for mathematics

Nonlinear algebra and optimization on rings are “hard”. (English) Zbl 0686.68037
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

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