When Input Integers are Given in the Unary Numeral Representation
Tomoyuki Yamakami
Many NP-complete problems take integers as part of their input instances.
These input integers are generally binarized, that is, provided in the form of
the "binary" numeral representation, and the lengths of such binary forms are
used as a basis unit to measure the computational complexity of the problems.
In sharp contrast, the "unarization" (or the "unary" numeral representation) of
numbers has been known to bring a remarkably different effect onto the
computational complexity of the problems. When no computational-complexity
difference is observed between binarization and unarization of instances, on
the contrary, the problems are said to be strong NP-complete. This work
attempts to spotlight an issue of how the unarization of instances affects the
computational complexity of various combinatorial problems. We present numerous
NP-complete (or even NP-hard) problems, which turn out to be easily solvable
when input integers are represented in unary. We then discuss the computational
complexities of such problems when taking unary-form integer inputs. We hope
that a list of such problems signifies the structural differences between
strong NP-completeness and non-strong NP-completeness.