Input: a bunch of binary strings: x_0, x_1, ... , x_n
Output: 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?