𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some Complexity Results for Polynomial Ideals

✍ Scribed by Ernst W. Mayr

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
184 KB
Volume
13
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we survey some of our new results on the complexity of a number of problems related to polynomial ideals. We consider multivariate polynomials over some ring, like the integers or the rationals. For instance, a polynomial ideal membership problem is a (w + 1)-tuple P = ( f, g 1 , g 2 , . . . , g w ) where f and the g i are multivariate polynomials, and the problem is to determine whether f is in the ideal generated by the g i . For polynomials over the integers or rationals, this problem is known to be exponential space complete. We discuss further complexity results for problems related to polynomial ideals, like the word and subword problems for commutative semigroups, a quantitative version of Hilbert's Nullstellensatz in a complexity theoretic version, and problems concerning the computation of reduced polynomials and GrΓΆbner bases.

πŸ“œ SIMILAR VOLUMES

Some Combinatorial Results for Complex R
Some Combinatorial Results for Complex Reflection Groups
✍ H. Can πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 160 KB

In this paper, we prove that a simple system for a subsystem of the complex root system can always be chosen as a subset of the positive system + of . Furthermore, we show that a set of distinguished coset representatives can be found for every reflection subgroup of the complex reflection groups. T

Algorithm for Computing Bernstein–Sato I
Algorithm for Computing Bernstein–Sato Ideals Associated with a Polynomial Mapping
✍ Rouchdi Bahloul πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 329 KB

Let f 1 , . . . , fp be polynomials in n variables with coefficients in a field K. We associate with these polynomials a number of functional equations and related ideals B, B j and B Ξ£ of K[s 1 , . . . , sp] called Bernstein-Sato ideals. Using standard basis techniques, our aim is to present an alg

Undecidability Results for Low Complexit
Undecidability Results for Low Complexity Time Classes
✍ Rod Downey; AndrΓ© Nies πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 165 KB

We prove that the theory of Exptime degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which was introduced by Nies (1997, Bull. London Math. Soc. 29, 683 692). The method can be applied