Перетасовка квадрата NP-завершена

Новые полные задачи NP всегда интересны, потому что они расширяют наши представления о том, что трудно вычислить. Теперь у нас есть новый результат, что перестановка квадратных строк NP-Hard.

Идея перемешивания очень проста. Возьмем две строки u и v, тогда w будет перемешиванием u и v, если существует набор строк xi и yi такой, что

u = x1 x2 · · · xk

а также

v = y1 y2 · · · yk

а также

w = x1 y1 x2 y2 · · · xk yk

Другими словами, w — это последовательное чередование подстрок строк v и w.

Строка w называется квадратом, если это перетасовка строки u с самой собой. То есть w можно создать путем перетасовки двух копий u.

Создавать квадраты легко; просто возьмите веревку и перемешайте ее с собой. Также обратите внимание, что одну строку можно перетасовать разными способами в зависимости от того, как вы разбили ее на подстроки.

Создать квадрат может быть легко, но гораздо сложнее решить обратную задачу определения того, является ли строка квадратной. Проблема определения того, может ли данная строка w быть выражена как перемешивание заданных u и v, может быть решена за полиномиальное время.

Вы даже можете решить более общую проблему: является ли w перемешиванием k различных строк за полиномиальное время, но только если k фиксировано. Если k не указано, проблема становится NP-полной. Позже это доказательство было распространено на случай, когда k строк идентичны, но до недавнего времени не было четкого ответа для квадратных строк, т.е. для случая k = 2.

То есть, можете ли вы найти полиномиальный алгоритм для определения того, что строка w может быть построена из перемешивания неопределенной строки u с самой собой?

Проблема квадрата кажется проще, чем общая проблема с k, которому разрешено варьировать, но на самом деле в недавней статье представлен результат, что она тоже является NP-полной, даже если алфавит, используемый для строк, конечен, но не слишком мал. Фактически в статье доказывается, что задача NP-полная для алфавитов размером до 7 символов. Это предполагает, что перемешивание всего с 3 символами может быть NP-полным, но нам все еще нужно доказательство этого.