# Finding steady-state solutions for ODE systems of zero, first and homogeneous second-order chemical reactions is NP-hard

Source: [Finding steady-state solutions for ODE systems of zero, first and homogeneous second-order chemical reactions is NP-hard](<https://www.sota2.com/research/paper/68fa64401e209131cea0378e>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:59:11.405Z

Authors: Marcelo S. Reis

Published: 2018-02-27T14:33:36.000Z

## Abstract

In the context of modeling of cell signaling pathways, a relevant step is finding steady-state solutions for ODE systems that describe the kinetics of a set of chemical reactions, especially sets composed of zero, first, and second-order reactions. To compute a steady-state solution, one must set the left-hand side of each ODE as zero, hence obtaining a system of non-negative, quadratic polynomial equations. If all second-order reactions are homogeneous in respect to their reactants, then the obtained quadratic polynomial equation system will also have univariate monomials. Although it is a well-known fact that finding a root of a quadratic polynomial equation system is a NP-hard problem, it is not so easy to find a readily available proof of NP-hardness for special cases like the aforementioned one. Therefore, we provide here a self-contained proof that finding a root of non-negative, with univariate monomials quadratic polynomial equation system (NUMQ-PES) is NP-hard. This result implies that finding steady-state solutions for ODE systems of zero, first and homogeneous second-order chemical reactions is a NP-hard problem; hence, it is not a feasible approach to approximate non-homogeneous second-order reactions into homogeneous ones.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1803.00618>)

[PDF](<https://arxiv.org/pdf/1803.00618.pdf>)
