For the most recent entries see the Petri Nets Newsletter.

It Is on the Boundary: Complexity Considerations for Polynomial Ideals.

Mayr, Ernst W.

In: LNCS 1872: Theoretical Computer Science - Exploring New Frontiers of Theoretical Informatics, pages 99-pp. International Conference IFIP TCS 2000, Sendai, Japan, August 2000. Proceedings / J. van Leeuwen, O. Watanabe, M. Hagiya, P.D. Mosses, T. Ito (Eds.) --- Springer Verlag, 2000.

Abstract: Systems of (in general non-linear but) polynomial equations over some ring or field R occur in numerous situations when dealing with problems in modelling, simulation, geometric representation and analysis, deduction, symbolic algebra, or dynamical systems, to name just a few. Algebraic varieties are determined by such systems (say over the reals or the complex number field), but they have also uses for propositional proof systems or for the modelling of certain parallel processes (as with reversible Petri nets). Many, if not most of the questions concerning such systems of polynomial equations reduce to the investigation of properties of polynomial ideals in multi-variate polynomial rings (like Q[x1,...,xn] or Z2[x1,...,xn], and earlier results have shown that such questions are generally very hard in the algorithmic sense, namely complete for the complexity class EXPSPACE.

As it turns out the algorithmic complexity of questions about polynomial ideals is really determined (as one might expect, of course) by the properties of the sets of exponent vectors occurring in the non-zero terms of the polynomials, and thus by the properties of seemingly well-structured subsets of Nn, the nonnegative orthant of Zn. The algorithmic properties of such subsets have been studied extensively in numerous areas, as mentioned above, and their complexity has consistently been misjudged, based on the fact that "far out", i.e., for sufficiently large values of the coordinates, most of the relevant algorithmic problems become easy (NP or even P).

Here, we discuss how properties at the boundary of Nn (to Zn) affect the algorithmic complexity of basic questions about polynomial ideals. We also present some new algorithmic and complexity theoretic results based on ideal dimension and other structural properties, like for toric ideals.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography