### Abstract

Every multivariate polynomial p(x), x = (x_{1},...,x_{n}) G [0, 1]^{n}, is enclosed in the interval given by the smallest and the greatest of its coefficients in the Tensorial Bernstein Basis (TBB). Knowing that the total number of these TBB coefficients is exponential with respect to the number of variables n, II^{n}_{i}=1(1 + d_{i}), even if all partial degrees di equal 1, a combinatorial problem arises: is it possible to compute in polynomial time the smallest and the greatest coefficients? This article proves that the 3-SAT problem, known to be NP-complete, polynomially reduces to the above defined combinatorial problem, which let us consequently conclude that this problem is NP-hard.

Original language | English (US) |
---|---|

Pages (from-to) | 22-33 |

Number of pages | 12 |

Journal | Reliable Computing |

Volume | 17 |

State | Published - Dec 2012 |

### Keywords

- Bernstein polynomials
- Combinatorial complexity
- Interval arithmetics
- Tensorial Bernstein Basis

### ASJC Scopus subject areas

- Software
- Computational Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'On the complexity of the Bernstein combinatorial problem'. Together they form a unique fingerprint.

## Cite this

*Reliable Computing*,

*17*, 22-33.