## 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[x_{1},…,x_{n}] or Z_{2}[x_{1},…,x_{n}]), 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 N^{n}, the nonnegative orthant of Z^{n}. 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 co- ordinates, most of the relevant algorithmic problems become easy (NP or even P). Here, we discuss how properties at the boundary of N^{n} (to Z^{n}) 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.

Original language | English |
---|---|

Title of host publication | Theoretical Computer Science |

Subtitle of host publication | Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings |

Editors | Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito |

Publisher | Springer Verlag |

Pages | 99 |

Number of pages | 1 |

ISBN (Print) | 3540678239, 3540678239, 9783540678236, 9783540678236 |

DOIs | |

State | Published - 2000 |

Event | 1st International Conference on Theoretical Computer Science, IFIP TCS 2000 - Sendai, Japan Duration: 17 Aug 2000 → 19 Aug 2000 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1872 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 1st International Conference on Theoretical Computer Science, IFIP TCS 2000 |
---|---|

Country/Territory | Japan |

City | Sendai |

Period | 17/08/00 → 19/08/00 |