On the complexity of the Bernstein combinatorial problem

Dominique Michelucci, Sebti Foufou, Arnaud Kubicki

Research output: Contribution to journalArticle

Abstract

Every multivariate polynomial p(x), x = (x1,...,xn) 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, IIni=1(1 + di), 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 languageEnglish (US)
Pages (from-to)22-33
Number of pages12
JournalReliable Computing
Volume17
StatePublished - 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

    Michelucci, D., Foufou, S., & Kubicki, A. (2012). On the complexity of the Bernstein combinatorial problem. Reliable Computing, 17, 22-33.