0
$\begingroup$

Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem? In other words, could the Tarski–Seidenberg theorem subsume Buchberger's algorithm and Wu's method?

Actually, algorithms of both Buchberger and Wu may be just deduced from variants of Hilbert's Nullstellensatz.

$\endgroup$
  • $\begingroup$ I'm not sure what point you are trying to make when you say "B and W may be just deduced from variants of HN." Is there some related question you mean to be asking with this sentence? $\endgroup$ – Joshua Grochow Oct 2 '17 at 15:38
8
$\begingroup$

For Buchberger, it depends what you want it for, but generally speaking the answer is no. First, as pointed out on the Wikipedia article, the complexity upper bound given by Tarski-Seidenberg is horrendous, whereas Buchberger's algorithm is exponential space, which is optimal (since ideal membership is EXPSPACE-complete).

Second, Tarski-Seidenberg is for semi-algebraic sets over the reals (that is, allowing $\leq, <, =, \neq$), whereas Buchberger's algorithm works not only for the reals, but for polynomials over any field, or even over other rings (such as $\mathbb{Z}$). With minor modifications, Buchberger's algorithm even works in various noncommutative analogues of polynomial rings.

Third, Grobner bases (and hence, Buchberger's algorithm) can be used for many more things besides quantifier elimination. For example, intersecting ideals, quotienting ideals, computing syzygy modules of ideals, proof systems (hence algorithms) for Tautologies, coding theory, group cohomology, applying toric geometry to algebraic geometry (where we think of the initial ideal as a way of deforming an arbitrary variety into a toric variety, and thereby learn things about the original variety that are easier to deduce for the toric one), the list goes on...

(I am less familiar with Wu's method.)

$\endgroup$
  • $\begingroup$ Are those things using Grobner bases isomorphic? For example, polynomials over field is isomorphic to complexes. $\endgroup$ – XL _at_China Oct 3 '17 at 2:59
  • 2
    $\begingroup$ @XL_at_China: Which "things using Grobner bases" are you referring to? And what do you mean by "polynomials over field is isomorphic to complexes"? $\endgroup$ – Joshua Grochow Oct 3 '17 at 19:13
  • $\begingroup$ regarding "things using Grobner bases",I just cite what you say in your answer. "polynomials over field is isomorphic to complexes" is not knowledge from algebraic geometry? $\endgroup$ – XL _at_China Oct 5 '17 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.