Return to Answer

If we allow straight line program representation as a valid compression of the input, then we can easily come up with many NP-hard equivalence test problems similar to the indexed binary decision diagrams problem given in the question. Asking whether two boolean formulas (given as straight line programs for the free Boolean ring, using the constants $0$, $1$, the unary minus operation, and the binary addition and multiplication operations) are distinct (non-equivalent) is actually NP-complete (and closely related to SAT). One could call this problem of distinguishing two elements of a free algebra given in straight line program representation the slp distinction problem. This problem is undecidable for the free modular lattice (on 4 or more generators). But for undecidable problems, it doesn't even matter whether we compressed the input or not, hence some people wrongly believe that it doesn't matter how the input is encoded (if it is only compressed).

If we allow straight line program representation as a valid compression of the input, then we can easily come up with many NP-hard equivalence test problems similar to the indexed binary decision diagrams problem given in the question. Asking whether two boolean formulas (given as straight line programs for the free Boolean ring, using the constants $0$, $1$, the unary minus operation, and the binary addition and multiplication operations) are distinct (non-equivalent) is actually NP-complete (and closely related to SAT). One could call this problem of distinguishing two elements of a free algebra given in straight line program representation the slp distinction problem. This problem is undecidable for the free modular lattice (on 4 or more generators). But for undecidable problems, it doesn't even matter whether we compressed the input or not, hence some people wrongly believe that it doesn't matter how the input is encoded (if it is only compressed).

This question reminds me of how annoyed I was about an unexpected definition of the ring isomorphism problem by Kayal and Saxena:

This question reminds me of how annoyed I was about an unexpected definition of the ring isomorphism problem by Kayal and Saxena:

This question reminds me of how annoyed I was about an unexpected definition of the ring isomorphism problem by Kayal and Saxena:

This question reminds me of how annoyed I was about an unexpected definition of the ring isomorphism problem by Kayal and Saxena: