Search code examples
algorithmalgebra

Can systems of multivariate cubic equations be solved in polynomial time in general?

To my knowledge, there exist polynomial-time algorithms for systems of multivariate quadratic equations, i.g., XL(eXtended Linearization). But I don't know if there exists a polynomial-time algorithm for a general system of multivariate cubic equations. Could anybody give an example for me? Thanks very much!

Solution

  • XL runs in polynomial time only if the system is overdefined.

    In general case, every system of multivariate nonlinear equations over GF(2) is equivalent to some 3-SAT instance. Hence the problem of finding solution is NP-hard.

    I can suggest two other methods, which are applicable in general (and in my cases were much faster than XL):