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
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
