The Post correspondence problem over a unary alphabet

P. Rudnicki, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
414 Downloads (Pure)


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 languageEnglish
Pages (from-to)723-727
Number of pages5
JournalApplied mathematics letters
Issue number5
Publication statusPublished - 2003


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


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

Cite this