Унарный язык
В теории сложности вычислений унарный язык или язык подсчета — это формальный язык (набор строк ), где все строки имеют форму 1 к , где «1» может быть любым фиксированным символом. Например, язык {1, 111, 1111} унарный, как и язык {1 к | k — простое число }. Класс сложности всех таких языков иногда называют TALLY .
Название «унарный» происходит от того факта, что унарный язык представляет собой кодировку набора натуральных чисел в унарной системе счисления . Поскольку вселенная строк в любом конечном алфавите представляет собой счетное множество , каждый язык может быть отображен в уникальный набор A натуральных чисел; таким образом, каждый язык имеет унарную версию {1 к | k в A}. И наоборот, каждый унарный язык имеет более компактную двоичную версию - набор двоичных кодировок натуральных чисел k таких, что 1 к есть в языке.
Поскольку сложность обычно измеряется длиной входной строки, унарная версия языка может быть «проще», чем исходный язык. Например, если язык можно распознать за O(2 н ) время, его унарную версию можно распознать за время O( n ), поскольку n стало экспоненциально большим. В более общем смысле, если язык можно распознать за время O(f( n )) и пространство O(g( n )) его унарная версия может быть распознана за время O( n + f(log n )) и за O(g (log n )) (нам требуется время O( n ) только для чтения входной строки). Однако если принадлежность к языку неразрешима , то и принадлежность к его унарной версии также неразрешима.
Отношения с другими классами сложности
[ редактировать ]TALLY содержится в P/poly — классе языков, которые можно распознать за полиномиальное время при наличии рекомендательной функции, зависящей только от длины входных данных. В этом случае требуемая рекомендационная функция очень проста — она возвращает один бит для каждой входной длины k, определяя, соответствует ли 1 к есть на языке или нет.
Унарный язык обязательно является разреженным языком , поскольку для каждого n он содержит не более одного значения длины n и не более n значений длины не более n , но не все разреженные языки являются унарными; таким образом, TALLY содержится в SPARSE .
Считается, что NP-трудных унарных языков не существует: если существует унарный язык, NP-полный , то P = NP . [1]
Этот результат можно распространить на разреженные языки. [2]
Если L — унарный язык, то L* ( звезда Клини языка L ) — регулярный язык . [3]
Классы подсчета
[ редактировать ]Класс сложности P 1 — это класс унарных языков, которые могут быть распознаны машиной Тьюринга с полиномиальным временем (при условии, что ее входные данные записаны в унарном языке); аналог класса P. это Аналогом NP в унарной установке является NP 1 . #P счетный класс 1 , аналог #P . Также известен [4]
Ссылки
[ редактировать ]Примечания
[ редактировать ]- ^ Петр Берман. Связь между плотностью и детерминированной сложностью NP-полных языков. В материалах 5-й конференции по автоматам, языкам и программированию , стр. 63–71. Спрингер-Верлаг. Конспект лекций по информатике №62 . 1978.
- ^ С.Р. Махани. Разреженные полные множества для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25:130-143. 1982.
- ^ «Звезда Клини бесконечного унарного языка всегда дает регулярный язык» . Обмен стеками в области компьютерных наук . Проверено 19 октября 2014 г.
- ^ Лесли Валиант , Сложность проблем перечисления и надежности , [1]
Общие ссылки
[ редактировать ]- Лэнс Фортноу. Любимые теоремы: Малые множества. 18 апреля 2006 г. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html .
- Зоопарк сложности : ТАЛЛИ