On the complexity of the Bernstein combinatorial problem

Dominique Michelucci; Sebti Foufou; Arnaud Kubicki

On the complexity of the Bernstein combinatorial problem

Dominique Michelucci, Sebti Foufou, Arnaud Kubicki

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Every multivariate polynomial p(x), x = (x₁,...,x_n) G [0, 1]ⁿ, 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ⁿ_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

Cite this

@article{01e069185fe74fe6b986f3d47fe0e8ee,

title = "On the complexity of the Bernstein combinatorial problem",

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.",

keywords = "Bernstein polynomials, Combinatorial complexity, Interval arithmetics, Tensorial Bernstein Basis",

author = "Dominique Michelucci and Sebti Foufou and Arnaud Kubicki",

year = "2012",

month = dec,

language = "English (US)",

volume = "17",

pages = "22--33",

journal = "Reliable Computing",

issn = "1385-3139",

publisher = "Springer Netherlands",

}

TY - JOUR

T1 - On the complexity of the Bernstein combinatorial problem

AU - Michelucci, Dominique

AU - Foufou, Sebti

AU - Kubicki, Arnaud

PY - 2012/12

Y1 - 2012/12

N2 - 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.

AB - 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.

KW - Bernstein polynomials

KW - Combinatorial complexity

KW - Interval arithmetics

KW - Tensorial Bernstein Basis

UR - http://www.scopus.com/inward/record.url?scp=84872711963&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84872711963&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84872711963

SN - 1385-3139

VL - 17

SP - 22

EP - 33

JO - Reliable Computing

JF - Reliable Computing

ER -

On the complexity of the Bernstein combinatorial problem

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this