97-78: Remarks on the equivalence problem for PL-sets

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