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:
“Mental health data from the 1950’s on middle-aged women showed them to be a particularly distressed group, vulnerable to depression and feelings of uselessness. This isn’t surprising. If society tells you that your main role is to be attractive to men and you are getting crow’s feet, and to be a mother to children and yours are leaving home, no wonder you are distressed.”
—Grace Baruch (20th century)
“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)