### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 723-727 |

Number of pages | 5 |

Journal | Applied mathematics letters |

Volume | 16 |

Issue number | 5 |

DOIs | |

Publication status | Published - 2003 |

### Keywords

- Computational Complexity
- NP-complete
- IR-45804
- Post correspondence problem
- METIS-213305
- Pseudopolynomial time algorithm

## Fingerprint Dive into the research topics of 'The Post correspondence problem over a unary alphabet'. Together they form a unique fingerprint.

## Cite this

Rudnicki, P., & Woeginger, G. (2003). The Post correspondence problem over a unary alphabet.

*Applied mathematics letters*,*16*(5), 723-727. https://doi.org/10.1016/S0893-9659(03)00073-9