  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.
