Why intervals? Because if we allow other sets, tractable problems become intractable (Q1276136)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Why intervals? Because if we allow other sets, tractable problems become intractable |
scientific article |
Statements
Why intervals? Because if we allow other sets, tractable problems become intractable (English)
0 references
9 September 1999
0 references
The complexity of computing the range of a polynomial, resp. a linear combination of computable in polynomial time monotonic functions over a region, which is either an interval or a finite union of intervals, is considered. It is shown that the problem is not NP-hard in the first case (interval region) and is NP-hard in the second case (multiinterval region).
0 references
interval arithmetic
0 references
complexity
0 references
range of a polynomial
0 references
monotonic functions
0 references
interval region
0 references
NP-hard
0 references
multiinterval region
0 references
