Input: a bunch of binary strings: x_0, x_1, ... , x_nOutput: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. the minimum number of insertions, deletions, and substitutions to transform x into y.What complexity class is this problem in? Does it have an efficient exact or approximation algorithm?
Find a string with minimal edit distance from a set of given strings
cc.complexity theory;ds.algorithms;search problem;edit distance
Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.