5
$\begingroup$

Given a set of multivariate, quadratic, non-homogeneous equations, is there a way to decide how many non-negative roots it have?

Some explanations:

  1. All the coefficients are real numbers.
  2. The number of variables is the same as the number of equations, and all the equations are independent.
  3. Some of the equations might actually be linear equations.
  4. By "non-negative" solution, I mean a solution in which all the variables take non-negative values.
  5. By some "physical" reasoning, we know it must have at least one non-negative solution.

Further explanations:

  1. I know generally a set of n quadratic equations with n variables has at most $2^n$ distinct roots.
  2. The background of this problem is: the set of quadratic equations is the right-hand side of the chemical rate equation. By equating is to zero, the steady-state case is being considered. As we only take one-body or two-body reactions into account, the degree of the equations are at most two. As the abundance of the molecules cannot be negative, we only care about the non-negative solutions.
  3. The number of variables can be up to 1000, so simple numerical test is not practical.

I am not a math student, and I am not sure whether this kind of question is allowed here.

$\endgroup$

1 Answer 1

4
$\begingroup$

Not efficiently, at least not unless the problem has some additional structure which can be exploited. The set of mixed Nash equilibria of a two-player game can be written as the nonnegative solutions of such a polynomial system. In general it is #P-hard to count the equilibria of such a game (Conitzer and Sandholm). It is even PPAD-hard (still thought to be polynomial time unsolvable) to compute a single equilibrium, although one is guaranteed to exist by Nash's Theorem.

You may want to investigate connections with Nash equilibria further -- if your problem is somehow equivalent to this one then you will have a lot of established results and techniques to build on. Also people would probably find a connection between game theory and chemistry surprising. Or if your problem is easier, looking at Nash equilibria might help you figure out what extra features your problem has that makes it solvable efficiently. If it is harder or incomparable it might still be interesting to know that.

$\endgroup$
1
  • $\begingroup$ The link to sciencedirect.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ May 14 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.