## DIMACS TR: 97-78

## Remarks on the equivalence problem for PL-sets

### Author: Bhaskar DasGupta

**
ABSTRACT
**

The following problem arises in connection with checking the
equivalence piecewise-linear (PL) sets.
Consider two-variable polynomials with non-negative integer coefficients,
and given two such polynomials, decide if they are equivalent to each
other modulo the following equalities $x=2x+1$, $y^2=2y^2+y$ and
$y=x+y+1$. In this paper, we show that this problem can be solved
in polynomials time in both the unit-cost and the logarithmic-cost model.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-78.ps.gz

DIMACS Home Page