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.
DIMACS Home Page