NP-hardness of deciding convexity of quartic polynomials and related problems

Amir Ali Ahmadi, Alex Olshevsky, Pablo A. Parrilo, John N. Tsitsiklis

Research output: Contribution to journalArticle

54 Scopus citations

Abstract

We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.

Original languageEnglish (US)
Pages (from-to)453-476
Number of pages24
JournalMathematical Programming
Volume137
Issue number1-2
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • 68Q25 Analysis of algorithms & problem complexity
  • 90C60 Abstract computational complexity for mathematical programming problems
  • Mathematics Subject Classification (2000): 90C25 Convex programming

Fingerprint Dive into the research topics of 'NP-hardness of deciding convexity of quartic polynomials and related problems'. Together they form a unique fingerprint.

  • Cite this