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 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 comple...
| Principais autores: | , , , |
|---|---|
| Outros Autores: | |
| Formato: | Artigo |
| Idioma: | en_US |
| Publicado em: |
Springer-Verlag
2012
|
| Acesso em linha: | http://hdl.handle.net/1721.1/73527 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-2658-8239 |