NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

Details NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

2010-12-09

arxiv.org/abs/1012.1908v1

Mathematics

Optimization and Control

20 pages

Scientific paper

10.1007/s10107-011-0499-2

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.

Affiliated with

Also associated with

No associations

Rating

NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76447