Vi visar att om inte P=NP, det finns ingen polynom tid (eller ens pseudo-polynom tid) algoritm som kan avgöra om en multivariat polynom av grad fyra (eller högre jämn grad) är globalt konvex. Detta löser ett problem som har varit öppet sedan 1992 när N. Z. Shor bad om komplexiteten i att besluta konvexitet för kvartiska polynomer. Vi bevisar också att beslut om strikt konvexitet, stark konvexitet, kvasikonvexitet och pseudokonvexitet av polynom av jämn grad fyra eller högre är starkt NP-hård. Däremot visar vi att kvasikonvexitet och pseudokonvexitet av udda grad polynom kan avgöras i polynom tid.
Det har visats i REF att testning om ett polynom av grad fyra är konvex är NP-hård i stark bemärkelse.
NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
{'venue': 'Mathematical Programming, Vol. 137, Issue 1-2, pp 453-476, 2013', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}