From: Richard Fateman <fateman@cs.berkeley.edu>
Subject: Re: computer algebra, beginner needs help
Date: Thu, 01 Jun 2000 07:43:49 -0700
Newsgroups: sci.math.symbolic
Summary: [missing]

twma wrote:
> 
> How do we know that two expressions are the same?
> For example, x^2+2x+sin^2x, (x+1)^2-cos^2x, are the same
> but where can I find algorithm to check them?
> 
Subtract one from the other to get an expression.
You now want to know if it is zero everywhere.
The zero-equivalence problem has been discussed most
thoroughly by Daniel Richardson in technical papers
over the years.

While the problem is in general not solvable by
a uniform algorithmic procedure, given a large enough
class of expressions, there are certainly some effective
procedures for subclasses, e.g. polynomials, exponential
polynomials, rational functions.

Evaluation doesn't do the job because it can't always detect
the difference between zero and a function that is
zero everywhere you checked, but not everywhere.  
Try plotting  f(x):=arctan(x)+arctan(1/x)-pi/2.  This is
zero for x>0.
You can make other functions from this..
RJF