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 π−1(s) will be a solution to the original instance. Example Given an instance with three input strings uvwx, xuwv, and xvwu. This could be written as a matrix like this: The first column has the values (u, x, x). As x is the character that appears the most often, we replace it by a, and we replace u, the second most often character, by b, obtaining the new first column (b, a, a). The second column has the values (v, u, v). As for the first column, v is replaced by a and u is replaced by b, obtaining the new second column (a, b, a). Doing the same with all columns gives the normalized instance Data reduction obtained from normalization Normalizing the input reduces the alphabet size to at most the number of input strings. This can be useful for algorithms whose running times depend on the alphabet size. Approximability Li et al. evolved a polynomial-time approximation scheme which is practically unusable because of the large hidden constants. Fixed-parameter tractability Closest String can be solved in , where k is the number of input strings, L is the length of all strings and d is the desired maximum distance from the solution string to any input string. Relations to other problems Closest string is a special case of the more general closest substring problem, which is strictly more difficult. While closest string turns out to be fixed-parameter tractable in a number of ways, closest substring is W[1]-hard with regard to these parameters. References NP-hard problems Formal languages