×

An NP-hardness result for nonlinear systems. (English) Zbl 0914.65058

The paper presents a system of nonlinear equations, the solution of which is NP-hard. Since it contains only linear and bilinear terms, it is simple looking and has many attractive features. On the other hand, a correspondence with a knapsack problem yields NP-hardness. Besides this, the paper contains several comments on interval analysis.
Reviewer: D.Braess (Bochum)

MSC:

65H10 Numerical computation of solutions to systems of equations
65Y20 Complexity and performance of numerical algorithms
65G30 Interval and finite arithmetic
Full Text: DOI