Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.)
