unary alphabet. We show that the complexity of this problem heavily depends on the representation of the input: the problem is NP-complete if the input is given in compact (logarithmic) form, whereas it becomes polynomially solvable if the input is encoded in unary.
- Computational Complexity
- Post correspondence problem
- Pseudopolynomial time algorithm