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 |