Find a string with minimal edit distance from a set of given strings 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?
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.