Recognizing Signomial Convexity Is Shown Strongly NP-Hard, Closing All Three Tractability Routes
The work studies convexity recognition for signomials (finite sums of generalized monomials with real exponents) and shows that deciding whether a signomial is convex in its original variables, becomes convex after a logarithmic change of variables, or, when positive, becomes convex after additionally taking the logarithm of its value (the structure underlying disciplined geometric programming) is strongly NP-hard, both on compact domains and globally, via reductions from gap-promise variants of polynomial convexity that preserve curvature gaps under the relevant logarithmic transformations.