Recognizing Signomial Convexity Is Shown Strongly NP-Hard, Closing All Three Tractability Routes

The paper proves that recognizing all three forms of signomial convexity—convexity in the original variables, convexity after a logarithmic change of variables, and, for positive signomials, convexity after additionally taking the logarithm of the value—is strongly NP-hard. Signomial optimization was already known to be computationally intractable in general, and convexity was treated as the route to tractability; this work pushes intractability to the recognition step itself. The abstract reports a complexity reduction: reductions start from gap-promise variants of polynomial convexity and preserve curvature gaps under the relevant logarithmic transformations, with the conclusion covering both compact domains and the global setting.

The paper frames signomials as a natural machine learning model that combines parsimonious representations of power laws, inverse relationships, and multiplicative interactions with universal approximation and interpretable parameters. This framing moves signomials from a classical engineering optimization object toward a machine learning representation, supported by the quantitative observation that 45 of the 100 equations in the AI Feynman benchmark admit signomial representations. The basis is the benchmark statistic stated in the abstract (45 of 100 equations) together with the stated representation properties, an observation about existing representational capacity rather than a new experiment.

The technical core is a reduction that preserves curvature gaps under the relevant logarithmic transformations, transferring the gap-promise hardness of polynomial convexity to signomial convexity recognition. This reduction shows that logarithmic transformations (and the logarithm of the value) do not serve as a general way around the hardness, giving the three routes a common source of difficulty. The abstract states that the proofs start from gap-promise variants of polynomial convexity and that the reductions preserve curvature gaps; the detailed construction is not expanded in the abstract.

The result applies to the signomial function class and covers three recognition forms: convexity in the original variables, convexity after a logarithmic change of variables, and, for positive signomials, convexity after taking the logarithm of the value; it addresses both compact domains and the global setting. For researchers in geometric programming, engineering design, and symbolic regression in machine learning, this means a general polynomial-time algorithm for deciding these convexity properties should not be expected; viable directions include restricting to structured subclasses, using approximate or numerical tests, or relying on global methods that do not require convexity recognition.

The abstract does not give the concrete reduction construction, the gap parameters, or the proof steps, nor does it state whether the conclusions still hold for restricted subclasses such as low-dimensional, sparse, or specially structured exponents; the criteria and coverage behind the 45-of-100 AI Feynman statistic are also not expanded in the abstract. These are information boundaries at the abstract level, and the theorem statements and proof details in the full paper would still need to be consulted.