В теории сложности вычислений , унарный язык или Tally язык является формальным языком (набор строк ) , где все строки имеют вид 1 K , где «1» может быть любым фиксированным символом. Например, язык {1, 111, 1111} унарный, как и язык {1 k | к является главным }. Класс сложности всех таких языков иногда называют TALLY .
Название «унарный» происходит от того факта, что унарный язык - это кодировка набора натуральных чисел в унарной системе счисления . Поскольку совокупность строк в любом конечном алфавите является счетным множеством , каждый язык может быть отображен в уникальное множество A натуральных чисел; таким образом, у каждого языка есть унарная версия {1 k | k в A}. И наоборот, каждый унарный язык имеет более компактную двоичную версию, набор двоичных кодировок натуральных чисел k таких, что в языке есть 1 k .
Поскольку сложность обычно измеряется длиной входной строки, унарная версия языка может быть «проще», чем исходный язык. Например, если язык может быть распознан за время O (2 n ), его унарная версия может быть распознана за время 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 k на языке или нет.
Унарный язык обязательно является разреженным языком , поскольку для каждого 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. Springer-Verlag. Конспект лекций по информатике №62 . 1978 г.
- ^ SR Mahaney. Редкие полные наборы для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25: 130-143. 1982 г.
- ^ -, Патрик. «Клини-звезда бесконечного унарного языка всегда дает регулярный язык» . Обмен стеком информатики . Проверено 19 октября 2014 года .CS1 maint: числовые имена: список авторов ( ссылка )
- ^ Лесли Вэлиант , Сложность проблем перечисления и надежности , [1]
Общие ссылки [ править ]
- Лэнс Фортноу. Любимые теоремы: малые множества. 18 апреля 2006 г. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html
- Зоопарк сложности : СЛОВО