Why intervals? Because if we allow other sets, tractable problems become intractable (Q1276136)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Why intervals? Because if we allow other sets, tractable problems become intractable |
scientific article; zbMATH DE number 1240633
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Why intervals? Because if we allow other sets, tractable problems become intractable |
scientific article; zbMATH DE number 1240633 |
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
