The Post correspondence problem over a unary alphabet

P. Rudnicki; Gerhard Woeginger

doi:10.1016/S0893-9659(03)00073-9

The Post correspondence problem over a unary alphabet

P. Rudnicki, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

426 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 language	English
Pages (from-to)	723-727
Number of pages	5
Journal	Applied mathematics letters
Volume	16
Issue number	5
DOIs	https://doi.org/10.1016/S0893-9659(03)00073-9
Publication status	Published - 2003

Keywords

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

Access to Document

10.1016/S0893-9659(03)00073-9

Woeginger03postFinal published version, 375 KB

Cite this

@article{20a1a9a628124a3297ad38c22c15a656,

title = "The Post correspondence problem over a unary alphabet",

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.",

keywords = "Computational Complexity, NP-complete, IR-45804, Post correspondence problem, METIS-213305, Pseudopolynomial time algorithm",

author = "P. Rudnicki and Gerhard Woeginger",

year = "2003",

doi = "10.1016/S0893-9659(03)00073-9",

language = "English",

volume = "16",

pages = "723--727",

journal = "Applied mathematics letters",

issn = "0893-9659",

publisher = "Elsevier Ltd",

number = "5",

}

TY - JOUR

T1 - The Post correspondence problem over a unary alphabet

AU - Rudnicki, P.

AU - Woeginger, Gerhard

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - Computational Complexity

KW - NP-complete

KW - IR-45804

KW - Post correspondence problem

KW - METIS-213305

KW - Pseudopolynomial time algorithm

U2 - 10.1016/S0893-9659(03)00073-9

DO - 10.1016/S0893-9659(03)00073-9

M3 - Article

SN - 0893-9659

VL - 16

SP - 723

EP - 727

JO - Applied mathematics letters

JF - Applied mathematics letters

IS - 5

ER -

The Post correspondence problem over a unary alphabet

Abstract

Keywords

Access to Document

Fingerprint

Cite this