The membership problem for unmixed polynomial ideals is solvable in single exponential time
From MaRDI portal
Publication:1180154
DOI10.1016/0166-218X(91)90109-AzbMath0747.13018WikidataQ127656619 ScholiaQ127656619MaRDI QIDQ1180154
Alicia Dickenstein, Noaï Fitchas, Marc Giusti, Carmen Sessa
Publication date: 27 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)
Related Items (30)
Finding sparse systems of parameters ⋮ Polly cracker, revisited ⋮ On the efficiency of effective Nullstellensätze ⋮ Unnamed Item ⋮ Bounds of traces in complete intersections and degrees in the Nullstellensatz ⋮ A global view of residues in the torus ⋮ Complexity of Membership Problems of Different Types of Polynomial Ideals ⋮ Polar varieties, real equation solving, and data structures: the hypersurface case ⋮ A Pommaret bases approach to the degree of a polynomial ideal ⋮ Straight-line programs in geometric elimination theory ⋮ A generalized Euclidean algorithm for geometry theorem proving ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ Bounds for degrees of syzygies of polynomials defining a grade two ideal ⋮ p-adic algorithm for bivariate Gröbner bases ⋮ Computing Circuit Polynomials in the Algebraic Rigidity Matroid ⋮ Computation of étale cohomology on curves in single exponential time ⋮ Using elimination theory to construct rigid matrices ⋮ Equations for the projective closure and effective Nullstellensatz ⋮ La queste del Saint \(\text{Gr}_ a(\text{AL})\): A computational approach to local algebra ⋮ An effective residual criterion for the membership problem in \(\mathbb{C} [z_ 1,\cdots{} ,z_ n\)] ⋮ On the bit complexity of polynomial system solving ⋮ Evaluating geometric queries using few arithmetic operations ⋮ Deterministic normal position transformation and its applications ⋮ Computing bases of complete intersection rings in Noether position ⋮ Incomplete Gröbner basis as a preconditioner for polynomial systems ⋮ On the index and the order of quasi-regular implicit systems of differential equations ⋮ Ideal membership in polynomial rings over the integers ⋮ Complexity bounds in elimination theory -- a survey. ⋮ Why you cannot even hope to use Gröbner bases in cryptography: an eternal golden braid of failures ⋮ On the complexity of the real Nullstellensatz in the 0-dimensional case
Cites Work
- On computing the determinant in small parallel time using a small number of processors
- Combinatorial dimension theory of algebraic varieties
- Bounds for the degrees in the Nullstellensatz
- Computing dimension and independent sets for polynomial ideals
- Résolution des systèmes d'équations algébriques
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Comments on the translation of my PhD thesis: ``An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
- Algèbre linéaire sur $K[X_1,\dots,X_n$ et élimination]
- Sharp Effective Nullstellensatz
- Complexity of standard bases in projective dimension zero
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The membership problem for unmixed polynomial ideals is solvable in single exponential time
