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:
“This city is neither a jungle nor the moon.... In long shot: a cosmic smudge, a conglomerate of bleeding energies. Close up, it is a fairly legible printed circuit, a transistorized labyrinth of beastly tracks, a data bank for asthmatic voice-prints.”
—Susan Sontag (b. 1933)
“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)