Simplifications and Data Reductions
Instances of closest string may contain information that is not essential to the problem. In some sense, the usual input of closest string contains information, that does not contribute to the hardness of the problem. For example, if some strings contain the character a, but none contains the character z, we could replace all as with zs and this modified instance would essentially be equivalent, that is: given a solution of the modified instance, we could tell the original solution and vice versa.
Read more about this topic: Closest String
Famous quotes containing the words data and/or reductions:
“To write it, it took three months; to conceive it three minutes; to collect the data in it—all my life.”
—F. Scott Fitzgerald (1896–1940)
“The work was like peeling an onion. The outer skin came off with difficulty ... but in no time you’d be down to its innards, tears streaming from your eyes as more and more beautiful reductions became possible.”
—Edward Blishen (b. 1920)