Normalizing The Input
When all input strings that share the same length are written on top of each other, they form a matrix. Now, we can see that certain row types have essentially the same implications to the solution. Say, given a column with three entries, (a,a,b), then we might change the solution string, but not the solvability, by replacing this column with another column (x,x,y), because they express the same structure. This structure being that the first two entries are the same while the third is different.
We can, in each column, replace the character that occurs the most often with a, the character that occurs the second most often, and so forth. An input instance with this property is called normalized.
If we have a solution to the modified instance, we can find the original instance by remapping the characters of the solution to its original version in every column.
The order of the columns does not contribute to the hardness of the problem. That means, if we permute all input strings according to a certain permutation and obtain a solution string s to that modified instance, then will be a solution to the original instance.
Read more about this topic: Closest String, Simplifications and Data Reductions
Famous quotes containing the word input:
“Celebrity is a mask that eats into the face. As soon as one is aware of being “somebody,” to be watched and listened to with extra interest, input ceases, and the performer goes blind and deaf in his overanimation. One can either see or be seen.”
—John Updike (b. 1932)