Как тяжело расставлять строки?

117

Перестановка двух строк формируется путем встраивания символов в новую строку, сохраняя символы каждой строки в порядке. Например, MISSISSIPPIэто перетасовка MISIPPи SSISI. Позвольте мне назвать строковый квадрат, если это тасование двух одинаковых строк. Например, ABCABDCDквадратный, потому что это перетасовка ABCDи ABCD, но строка ABCDDCBAне квадрат.

Существует ли быстрый алгоритм для определения того, является ли строка квадратной или NP-трудной? Очевидный подход динамического программирования, похоже, не работает.

Даже следующие особые случаи кажутся сложными: (1) строки, в которых каждый символ встречается не более четырех- шести раз, и (2) строки только с двумя разными символами. Как указывает Пер Острин ниже, частный случай, когда каждый персонаж встречается не более четырех раз, может быть уменьшен до 2SAT.


Обновление: у этой проблемы есть другая формулировка, которая может упростить проверку твердости.

Рассмотрим граф G, вершинами которого являются целые числа от 1 до n; идентифицировать каждое ребро с реальным интервалом между его конечными точками. Мы говорим, что два ребра G вложены, если один интервал правильно содержит другой. Например, ребра (1,5) и (2,3) являются вложенными, а (1,3) и (5,6) - нет, а (1,5) и (2,8) - нет. Совпадение в G не является вложенным, если нет пары ребер. Существует ли быстрый алгоритм для определения того, имеет ли G не вложенное идеальное соответствие, или эта проблема NP-трудная?

  • Отмена перестановки строки эквивалентна нахождению не вложенного идеального совпадения в непересекающемся объединении кликов (с ребрами между равными символами). В частности, отмена перестановки двоичной строки эквивалентна нахождению не вложенного идеального совпадения в непересекающемся объединении двух клик. Но я даже не знаю, сложна ли эта проблема для общих графов или для каких-либо интересных классов графов.

  • Существует простой алгоритм полиномиальное время , чтобы найти идеальный Непро- пересечения паросочетания.


Обновление (24 июня 2013 г.): проблема решена! Теперь есть два независимых доказательства того, что идентификация квадратных строк является NP-полной.

Существует также более простое доказательство того, что поиск не вложенных совершенных соответствий является NP-трудным, благодаря Шуай Ченг Ли и Мин Ли в 2009 году. См. « О двух открытых задачах 2-интервальных паттернов », Теоретическая информатика 410 (24–25). ): 2410–2423, 2009.

Jeffε
источник
2
Разве последовательность не является просто A000984, «числом возможных значений двоичного числа размером 2 * n, для которого половина битов включена, а половина выключена»?
Трэвис Браун
5
@Travis, если я не понимаю: для n = 4 10000111 - это 2 * n-битное двоичное число, для которого половина битов включена, а половина выключена, но это не квадрат, как определено. Следуя этой логике, поскольку квадраты являются строгим подмножеством множества, которое генерирует A000984, значения для квадратов над двоичным алфавитом должны быть ниже при равных индексах в последовательности - нет?
Даниэль Апон
1
Наблюдение: используя формализм графа, пусть 2n будет числом вершин в G. Пусть G ′ будет графом, полученным из линейного графа G путем добавления ребер между вершинами, соответствующих вложенным ребрам G. Задача задает вопрос, имеет ли G ′ независимый набор размером п. Существуют различные классы графов, где максимальное независимое множество может быть вычислено за полиномиальное время. Если мы пойдем этим путем, вопрос в том, какими хорошими свойствами обладает G ′? (подробнее)
Цуёси Ито
2
@Radu: Я не думаю, что доля квадратов в неквадрат (по двоичным алфавитам) сходится к 1/3. Я сделал несколько симуляций Монте-Карло, которые указывают на медленную сходимость к 1/2. Следовательно, в пределе по существу все двоичные строки с четными числами 0 и 1 являются квадратами. Это удивительно для меня и может быть использовано в алгоритме. Для больших алфавитов доля квадратов быстро сходится к 0.
Мартин Бергер
8
Поскольку этот вопрос упоминается в сегодняшнем сообщении в блоге, давайте посмотрим, сможем ли мы вновь проявить интерес к решению этой проблемы. Прошел год с тех пор, как этот вопрос был выдвинут, и с тех пор у нас появилось много новых пользователей. Я поднял награду в 100 представителей за этот вопрос.
Алекс тен Бринк

Ответы:

66

Майкл Солтис и я сумели доказать, что проблема определения возможности записи строки в виде квадратного тасования является NP-решением. Это применимо даже к конечному алфавиту с только различными символами, хотя наше доказательство написано для алфавита с 9 символами. Этот вопрос все еще открыт для небольших алфавитов, скажем, только с 2 символами. Мы не рассматривали проблему под ограничением, что каждый символ появляется только 6 раз (или, в более общем случае, постоянное число раз); так что этот вопрос все еще открыт.7926

В доказательстве используется сокращение от части. Публикация здесь слишком длинна, но препринт «Отмена перемешивания строки - NP- hard» доступен на наших веб-страницах по адресу:3NP

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

а также

http://www.cas.mcmaster.ca/~soltys/#Papers .

Статья была опубликована в журнале компьютерных систем наук:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Сэм Бусс
источник
11
Потрясающие!! (И к моему огромному облегчению, серьезно нетривиальным.)
Джеффс
15
Благодарю. StackExchange был нашим источником для этого вопроса. Это отличный ресурс!
Сэм Бусс
9
@SamBuss небольшая просьба: пока вы цитируете вопрос Джеффа, вы упоминаете только решение Пера Острина в тексте. Если вы посмотрите на ответы, есть способ также создать формальную цитату для ответов (нажмите кнопку «Поделиться» и нажмите ссылку «цитировать»). Таким образом, вы также можете создать правильную цитату для ответа Пера. Я упоминаю об этом только для того, чтобы люди, которые делают официальные вклады на сайте, также могли получить официальное признание. Спасибо ! и поздравляю за решение этой проблемы
Suresh Venkat
2
@SureshVenkat. Спасибо за совет: это полезно. Я добавил это в онлайн-версию статьи.
Сэм Бусс
Проблема распознавания квадратного тасования теперь оказалась сложной даже для двоичного алфавита: sciencedirect.com/science/article/pii/S0304397519300258
a3nm
58

Для особого случая, который вы упоминаете, когда каждый символ появляется максимум четыре раза, есть простое сокращение до 2-SAT (если я что-то упустил ...), как показано ниже:

Важным моментом является то, что для каждого персонажа существует (не более) двух допустимых способов сопоставления вхождений персонажа (третья возможность будет вложения). Используйте логическую переменную для представления, какое из двух совпадений выбрано. Теперь присваивание этим переменным дает правильное расстановку строк iff для каждой пары ребер, которые вложены, но не оба были выбраны. Это условие может быть точно описано дизъюнкцией переменных (возможно, с отрицанием), соответствующих двум задействованным символам.

За австрина
источник
Приятно. Эта же идея обобщает строки, где каждый символ встречается не более шести раз, но результатом является экземпляр 5-SAT. :-(
Джеффс
2
Этот ответ является любимым, чтобы выиграть награду.
Джефф
так что это, кажется, доказывает, что проблема в NPC, и почему нам нужны длинные доказательства конференций и журналов?
T ....
@ Турбо Сильно запоздалый, но это не доказывает, что проблема в том, чтобы быть NPC, потому что 2-SAT не NPC; это в П.
Стивен Стадницки,
Работает ли это сокращение до 2-SAT, если размер алфавита неограничен?
Мухаммед Аль-Туркистани
11

Вот алгоритм, который может иметь некоторые шансы быть правильным, хотя это сложно доказать, и я бы не стал ставить на это дом ...

Будем говорить , что будет очищен , если для каждого ребра е , существует (возможно , вложенная) совершенное соответствие G , который использует е и не использует край , содержащийся в или содержащие е .граммеграммее

Легко проверить , очищен ли и не найдены ли нарушающие края. Ясно, что ни одно из этих нарушающих ребер не может быть использовано в идеальном сопоставлении без вложенности G , поэтому его можно исключить из рассмотрения. Повторяя этот процесс, мы получаем (единственный) очищенный подграф G, который имеет не вложенное совершенное совпадение, если G имеет.граммграммграммграмм

Теперь наступает скачок веры, который может быть или не быть правильным: надежда состоит в том, что в очищенном графе, если все еще есть вершины степени , мы можем сделать жадный выбор и сопоставить первую такую ​​вершину с ее первым соседом. (или, что то же самое, удалите ребра для всех остальных соседей).>1

После жадного выбора мы снова очищаем график и т. Д., И процесс заканчивается, когда граф (надеюсь) не является идеальным соответствием без вложенности.

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

За австрина
источник
Я скептически отношусь ко второй жадной фазе, но очистка графика кажется полезной. В исходном строковом контексте, где граф представляет собой несвязанное объединение клик, можете ли вы что-нибудь сказать о структуре очищенного графа? Это все еще непересекающийся союз клик? (Другими словами, можете ли вы разделить вхождения каждого символа во входной строке, чтобы символы в разных частях не могли быть сопоставлены?)
Джеффс
2
Для второго вопроса рассмотрим строку «aaaa». Продувка удаляет края 1-4 и 2-3, давая 4 цикла. Два варианта второго жадного шага, которых также было бы достаточно, и я не мог найти никаких контрпримеров: 1) У очищенного графа есть не вложенное идеальное совпадение, если оно имеет идеальное совпадение (это кажется несопоставимым с жадным шагом) , 2) В очищенном графе с идеальным сопоставлением без вложенности каждое ребро используется в некотором идеальном сопоставлении без вложенности (это сильнее, чем жадный шаг и первый элемент, поэтому его легче опровергнуть).
За Австрина
11

Решение, которое мы с Сэмом Буссом предложили в ноябре 2012 года (показывающее, что отмена квадрата в NP-hard путем сокращения с 3-х разделов) теперь является опубликованной статьей в журнале Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Майкл Солтис
источник
2
Это действительно должно быть изменение к более раннему ответу Сэма Бусса, а не отдельный ответ. Вы можете нажать «изменить», чтобы предложить изменить ответ другого пользователя, и ваши изменения будут просмотрены другими пользователями сайта.
DW
11

Ромео Рицци и Стефан Виалетт доказывают, что распознавание квадратных строк является NP-завершенным в их статье 2013 года « О распознавании слов, являющихся квадратами для случайного произведения », путем сокращения из самой длинной проблемы двоичной подпоследовательности. Они утверждают, что сложность откатывания двоичных строк все еще открыта.

Еще более простое доказательство того, что нахождение не вложенного идеального соответствия является NP-полным, даны Шуай Ченг Ли и Мин Ли в их статье 2009 года « О двух открытых задачах 2-интервальных паттернов ». Однако они используют терминологию, унаследованную от биоинформатики. Вместо «идеального не вложенного соответствия» они называют это « проблемой DIS-2-IP- {<,} ». Эквивалентность между этими двумя проблемами описана Блиным, Фертином и Виалеттой :

Задача 2-IP-DIS- {<,} имеет непосредственную формулировку в терминах ограниченных сопоставлений в общих графах: для данного графа G вместе с линейным порядком π вершин группы G 2-IP-DIS- {<,} эквивалентна нахождению максимальной мощности, совпадающей с M в G со свойством, которое для любых двух различных ребер {u,v} и {u,v} из M ниmin{π(u),π(v)}<min{π(u),π(v)} иmax{π(u),π(v)<max{π(u),π(v)} ниmin{π(u),π(v)}<min{π(u),π(v)} иmax{π(u),π(v)}<max{π(u),π(v)} происходят.

Обновление (25 февраля 2019 г.): Булто и Виалетт показали, что проблема решения проблемы перетасовки двоичной строки в их статье является NP-полной. Распознавание двоичных квадратов тасования является NP-сложной задачей .

Мухаммед Аль-Туркистани
источник
Я не вижу связи, и я не вижу, где авторы утверждают, что отмена перестановки строки эквивалентна их проблеме.
Суреш Венкат
2
Они не говорят, что это равносильно перестановке; это более общая проблема.
Джефф
@SureshVenkat Я отредактировал свой ответ, надеюсь, он понятнее. По сути, в сноске говорится, что любые два ребра в сопоставлении ( ) не являются вложенными. M
Мохаммед Аль-Туркистани
В фактической опубликованной версии эквивалентность указана на странице 320. books.google.com/…
Мохаммад Аль-Туркистани
Отредактировано, чтобы убрать Леду .
Джеффс
9

Это помогает?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

Аарон Стерлинг
источник
7
Хорошая ссылка. Трудно понять, как результаты применимы к моей проблеме, но, возможно, методы помогут. Легко определить, является ли данная строка X тасованием двух копий другой данной строки Y. Прикрепленный документ доказывает, что NP-трудно решить, является ли данная строка X тасовкой любого числа копий другой данной строки Y. Я хочу знать, является ли данная строка X
тасовкой
5

НИКОГДА НЕ НАМ, ЭТО ОТВЕТ НЕПРАВИЛЬНЫЙ. Ошибка при вводе «AABAAB»: жадное сопоставление первых двух букв A делает невозможным сопоставление оставшихся символов. Я оставляю это, а не удаляю это, чтобы помочь другим избежать той же самой ошибки.

Мне кажется, что всегда безопасно сопоставлять каждый последующий символ предполагаемого квадрата с другим равным символом, который находится на как можно более ранней позиции. То есть, я думаю, что следующий алгоритм линейного времени должен работать:

Перебрать каждую позицию i во входной строке, i = 0, 1, 2, ... n. Для каждой позиции i проверьте, сопоставлена ​​ли уже эта позиция с какой-либо более ранней позицией в строке. Если нет, сопоставьте его с равным символом, который следует за последней уже найденной позицией и в противном случае находится как можно раньше в строке. Если совпадение не найдено для какого-либо символа, объявите, что ввод не является квадратом; в противном случае это набор символов в первой паре каждого совпадения.

Вот это в Python:

def sqrt (S):
    спички = []
    i, j = 0, 0
    пока я <len (S):
        если j <len (соответствует) и соответствует [j] [1] == i:
            я + = 1
            j + = 1
            Продолжить
        если совпадает:
            k = соответствует [-1] [1] + 1
        еще:
            к = 1
        в то время как k <len (S) и S [k]! = S [i]:
            k + = 1
        если k> = len (S):
            поднять Исключение («Не квадрат»)
        matches.append ((I, K))
        я + = 1
    return "" .join (S [a] для a, b в совпадениях)

печать sqrt ("ABCABDCD")

Здесь i - переменная основного цикла (позиция, которую мы пытаемся сопоставить), j - указатель на массив совпадающих пар, который ускоряет проверку того, совпадает ли позиция i, и k - индекс, используемый для поиска символ, который соответствует одному в позиции i. Это линейное время, потому что i, j и k монотонно растут по строке, и каждая итерация внутреннего цикла увеличивает одну из них.

Дэвид Эппштейн
источник
4
Был там. Сделано это. :-)
Джефф
5

Обновление: не имеет смысла говорить о сложности поиска идеального соответствия, которое не является вложенным и не пересекается, когда метки имеют значение от 1 до n, потому что есть только один такой. (Да, бьюсь о себе.) Однако, это имеет смысл, учитывая больший диапазон на этикетках ... так что я все еще вижу некоторую надежду, но это может быть совершенно бессмысленным в конце концов. Я, конечно, должен был бы продолжить это еще немного.


Я могу думать о том, почему может быть трудно найти соответствие, которое не является вложенным и не пересекается. Позвольте мне назвать такое соответствие непересекающимся соответствием . Не уверен, насколько это помогает, но позвольте мне представить обоснование в любом случае. (Я должен отметить, что мой аргумент в том виде, в котором он здесь представлен, не является полным, и детали, которые я опускаю, возможно, имеют решающее значение. Однако я полагаю, что это может быть чем-то вроде начала.)

граммК1N

КК

a1,...,aКК

NN1NUvaя(U,v)я

ККК

Чтобы избавиться от цветов и сделать идеальное совпадение, хотя и в более широком диапазоне , внесите следующие изменения в созданный таким образом график:

UaaUaA(A-2)Ua

Ua

[1] О задачах без полиномиальных ядер , Ханс Л. Бодлендер, Родни Г. Дауни, Майкл Р. Феллоуз и Дэнни Хермелин, Дж. Компут. Сист. Sci.

Neeldhara
источник
3
Я не совсем понимаю. Разве (1,2), (3,4), (5,6), ..., (n-1, n) не являются ЕДИНСТВЕННЫМИ непересекающимися соответствиями?
Джефф
Как только я перехожу к сценарию «идеального соответствия», я изменяю конструкцию и добавляю много новых вершин (обратите внимание, что я добавляю | U_a | -2 новых вершины для каждого a в алфавите). Таким образом, n взорвется соответственно - примерно до 2n-2k для алфавита размера k. Я надеюсь, что дал понять, что сокращение является неполным, поскольку я не указал, какие числа выделены для новых вершин, но я надеюсь, что его можно расширить без особых сложностей. Тем не менее, я, конечно, должен подумать об этом, прежде чем сказать что-то еще.
Нилдхара
1
Я думаю, что смысл комментария Джеффа состоит в том, что легко найти идеальное соответствие, которое не является вложенным и не пересекается (или сообщает об его отсутствии), потому что есть только одна возможность.
Цуёси Ито
2
Я не говорю о содержании вашей идеи доказательства, но я говорю о первом предложении вашего ответа: «Я могу подумать о том, почему может быть трудно найти идеальное соответствие, которое не является вложенным и непересекающимся». Эта задача проста по той причине, что написал Джефф.
Цуёси Ито
2
Без ограничения раскраски, налагаемого проблемой непересекающихся факторов (не более одного ребра каждого цвета), найти максимальное непересекающееся совпадение также легко.
Джефф
1

Подход не работает: декомпозиция перетасованного квадрата путем извлечения двух совпадающих букв не приводит к перетасовыванию квадратов ... См. Комментарии Раду ниже.


Σ

S(XY)A(Икс,Y)(1)A(aИкс1,aИкс2Y1Y2)A(Икс1,Y1)A(Икс2,Y2)(2)A(ε,ε)ε(3)
aΣε

Икс1Y1Y1Икс2Y2Y1Y2Икс1Икс2

aбсaбdсd

S(aбсaбdсd)A(aбс,aбdсd)(по 1,Иксзнак равноaбс,Yзнак равноaбdсd)A(бс,бdсd)A(ε,ε)(по 2,Икс1знак равнобс,Y1знак равнобdсd,Икс2знак равноY2знак равноε)A(с,с)A(d,d)A(ε,ε)(по 2)A(ε,ε)A(ε,ε)A(d,d)A(ε,ε)(по 2)A(ε,ε)A(d,d)A(ε,ε)(по 3)A(d,d)A(ε,ε)(по 3)A(ε,ε)A(ε,ε)A(ε,ε)(по 2)3εт.е. успех

0011

S(0011)A(0,011)A(ε,ε)A(1,1)A(1,1)*ε

ИксY

Сильвен
источник
ε
Я так не думаю.
Серж Гасперс
ε
Спасибо за возвращение; Я немного изменил грамматику, и даже у меня есть небольшая интуиция, которая может сработать.
Сильвен
3
ε
1

Обновить: Как отмечает Цуёси Ито в комментариях, этот алгоритм имеет экспоненциальное время выполнения.

Исходное сообщение:

Вот как я бы запрограммировал это в реальном мире.

Нам дана строка S = (S [1], ..., S [n]). Для каждого префикса S_r = (S [1], ..., S [r]) существует набор {(T_i, U_i)} пар строк, такой, что S_r является случайным образом (T_i, U_i), и T_i является префиксом U_i (то есть U_i 'начинается с' T_i). Сам S_r является квадратом тогда и только тогда, когда этот набор содержит пару (T_i, U_i) с T_i = U_i.

Теперь нам не нужно генерировать все эти пары; нам просто нужно сгенерировать суффикс V_i каждой строки U_i, полученной путем удаления ее копии T_i. Это исключит (возможно, экспоненциальное) количество ненужных дубликатов. Теперь S_r является квадратом тогда и только тогда, когда этот набор суффиксов содержит пустую строку. Таким образом, алгоритм становится:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Например, если S является AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Мы можем отбросить все суффиксы, длина которых превышает половину входной строки, поэтому это упрощается до:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

Я запрограммировал это на C ++, и это работает на всех приведенных здесь примерах. Я могу опубликовать код, если кому-то интересно. Вопрос в том, может ли размер SuffixSet расти быстрее, чем полиномиально?

TonyK
источник
3
Я тоже это попробовал, но эксперименты показывают, что размер SuffixSet, по-видимому, растет экспоненциально по n, если исходная строка (AB) ^ n.
Цуёси Ито
1

РЕДАКТИРОВАТЬ: Это неправильный ответ.


Сильвен предложил RCG, который, к сожалению, не подходит для этих «случайных квадратов». Тем не менее, я думаю, что есть один (РЕДАКТИРОВАТЬ: не RCG, см. Комментарии Курта ниже!) , Который выглядит следующим образом:

S(Y)A(ε,Y)(1)A(Икс,ZY)A(ИксZ,Y)(2)A(aИкс,aY)A(Икс,Y) для каждого aΣ(3)A(ε,ε)ε(4)

Объяснение: напомним, что мы должны сопоставлять символы, которые могут появляться в любом месте строки, но как только мы сопоставим aa'бб'aбa'б'(1,2)(3)(2) и посмотреть, есть ли совпадение в более поздней позиции. Важно то, что это разрешено только в одном направлении!

100110101010

S(100110101010)A(ε,100110101010)(1)A(1001,10101010)(2)*A(01,101010)(3)A(011,01010)(2)*A(1,010)(3)A(10,10)(2)*A(ε,ε)(3)ε(4)

Я не разработал формального доказательства того, что эта грамматика действительно отражает именно «случайные квадраты», но это не должно быть слишком сложно. Сильвен уже упоминал, что проблема решения для RCGs является полиномиальной.

DaniCL
источник
A(Икс,ε)23
5
@DaniCL, если подумать ... Должны ли параметры в RHS правил производства быть смежными диапазонами ввода? Я не видел этого явно в определении в статье Булье, но, похоже, именно так оно и используется. При анализе времени выполнения алгоритма синтаксического анализа он говорит, что число возможных аргументов к предложениям равно O (n ^ 2h), где h - максимальное количество предложений, а n - длина ввода. В вашей грамматике XZ в общем случае не будет смежным в исходном вводе.
Курт
3
@ Курт, я думаю, ты нашел недостаток. В другой статье («Китайские числа, MIX, скремблирование и грамматика конкатенации диапазонов») Булье прямо заявляет: «Конечно, только последовательные диапазоны могут быть объединены в новые диапазоны. В любой PRCG терминалы, переменные и аргументы в предложении являются должен быть привязан к диапазонам с помощью механизма замещения ". Это, вероятно, означает, что моя грамматика не является действительной RCG, что сомнения Раду были разумными, и что этот подход тоже не работает.
DaniCL
2
@ Курт правильный. Без ограничения смежности я почти уверен, что смогу создать набор производственных правил, которые распознают NP-полный язык UNARY 3PARTITION. Любой набор неотрицательных целых чисел может быть закодирован в унарном виде строкой на языке (1 * 0) ^ *. UNARY 3PARTITION - это набор всех таких строк, кодированный набор которых может быть разбит на 3-элементные подмножества, все с одинаковой суммой. (См en.wikipedia.org/wiki/3-partition_problem .)
Jeffε
1
Грамматика для 3-х частей: S (X0Y0Z) -> A (e, X0, Y0, Z); (W, 1X, Y, Z), А (W, X, 1Y, Z), (W, X, Y, 1Z) -> А (W1, X, Y, Z); (W, 0X, 0Y, 0Z) -> В (Вт, XYZ); В (Ш, е) -> е; В (Вт, X0Y0Z) -> С (W, W, X0, Y0, Z); С (Вт, 1V, 1X, Y, Z), С (Ш, 1V, Х, 1Y, Z), С (Ш, 1V, X, Y, 1Z) -> С (W, V, X, Y, Z); C (W, e, X, Y, Z) -> B (W, XYZ)
Раду ГРИГОР