An NP-hardness result for nonlinear systems

DOI10.1023/A:1024463631728MaRDI QIDQ1276126zbMATH OpenOpenAlexFDO

Authors Christian Jansson

Publication date 7 June 1999

Published in Reliable Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1024463631728

zbMATH Keywords

interval analysisNP-hardnesssystem of nonlinear equations

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)

Review text

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.

Recommendations

• Checking bounds on solutions of linear interval equations is NP-hard
• NP-hard classes of linear algebraic systems with uncertainties
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
• Nonlinear Algebra and Optimization on Rings are “Hard”

Cited in

(10)

• Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
• NP-hard classes of linear algebraic systems with uncertainties
• Scaling a Unitary Matrix
• Nonlinear Algebra and Optimization on Rings are “Hard”
• scientific article; zbMATH DE number 7599997 (Why is no real title available?)
• Dynamical Systems Theory and Algorithms for NP-hard Problems
• A Non-2-step Nilsystem With Linear Polynomial Complexity
• Employing the cloud for finding solutions to large systems of nonlinear equations
• Generalized analysis of methods for solving systems of nonlinear equations with point and interval coefficients
• On finding all roots to systems of nonlinear equations using large language models

This page was built for publication: An NP-hardness result for nonlinear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1276126)