Проблема исправления строки в строку доказательство np-полноты

Question

У меня есть это задание, чтобы доказать, что эта проблема:

Конечный алфавит £, две строки x, y € £ *, и положительное целое число K. есть способ получить строку у из строки x последовательностью K или меньше операций одного символа удаление или соседний символ взаимообмен

является np-полным. Я уже понял, что мне нужно выполнить преобразование из решающей версии проблемы покрытия множества, но я понятия не имею, как это сделать. Любая помощь будет оценена.

Answer 1

Выглядит как измененный Расстояние Левенштейна .Проблема может быть решена с помощью DP за квадратичное время.

Преобразование из минимального заданного покрытия (MSC) в эту проблему исправления строки описано в:

Robert A. Wagner
On the complexity of the Extended String-to-String Correction Problem
1975, Proceedings of seventh annual ACM symposium on Theory of computing 

Вкратце с проблемой MSC:

Для заданных конечных множеств x_1, ..., x_n и целого числа L существует ли подмножество J из {1, ..., n} такое, что | J |<= L и </p>

union_ {j in J} x_j = объединение всех x_i?

Пусть w = объединение всех x_i, пусть t = | w |и r = t ^ 2, и выберите символы Q, R, S, не входящие в w.

Взять строки:

A = Q^r R x_1 Q^r S^(r+1) ... Q^r R x_n Q^r S^(r+1)
B = R Q^r ... R Q^r w S^(r+1) ... S^(r+1)   <- each ... is n times
and
k = (l+1)r - 1 + 2t(r+1)(n-1) + n(n-1)(r+1)^2/2 + (r*n + |x_1 ... x_n| - t)*W_d
[W_d is delete operation weight, can be 1.]

Показано, что проблемы исправления строки-строки (A, B, k) выполнимо, если исходная проблема MSC:

Из построения строк ясно, что доказательство не тривиально :-) Но оно не слишком сложно для управления.

Answer 2

Упомянутое доказательство твердости NP работает только для произвольно больших алфавитов. Для конечных алфавитов проблема полиномиального времени, см. https://dblp.org/rec/bibtex/journals/tcs/Meister15