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

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