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

• 成果类型: Article
• 署名作者: Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N.
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0499-2
• 发表日期: 2013
• 页码: 453-476
• 关键词: Complexity; REPRESENTATION; criteria

摘要

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.