The Post correspondence problem over a unary alphabet

P. Rudnicki, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
119 Downloads (Pure)

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