ENCLOSING SOLUTIONS OF LINEAR INTERVAL EQUATIONS IS NP-HARD

Authors
ROHN J
Citation
J. Rohn, ENCLOSING SOLUTIONS OF LINEAR INTERVAL EQUATIONS IS NP-HARD, Computing, 53(3-4), 1994, pp. 365-368
Citations number
7
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Computing → ACNP
ISSN journal
0010485X
Volume
53
Issue
3-4
Year of publication
1994
Pages
365 - 368
Database
ISI
SICI code
0010-485X(1994)53:3-4<365:ESOLIE>2.0.ZU;2-O
Abstract
We show that if the conjecture P not equal NP is true, then there does not exist a general polynomial-time algorithm for enclosing the solut ion set of a system of linear interval equations.