Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Deciding polynomial convexity is NP-hardOptimization
|Speaker: ||Amirali Ahmadi, MIT|
|Location: ||1147 MSB|
|Start time: ||Tue, Mar 15 2011, 4:10PM|
We show that unless P=NP, there exists no polynomial time
pseudo-polynomial time) algorithm that can decide whether a
polynomial of degree four (or higher even degree) is globally convex.
solves a problem that has been open since 1992 when N. Z. Shor asked
complexity of deciding convexity for quartic polynomials. We also
deciding strict convexity, strong convexity, quasiconvexity, and
pseudoconvexity of polynomials of even degree four or higher is
NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity
degree polynomials can be decided in polynomial time.