WikiDer > Унарный язык

Unary language

В теория сложности вычислений, а унарный язык или же счетный язык это формальный язык (набор струны), где все строки имеют вид 1k, где «1» может быть любым фиксированным символом. Например, язык {1, 111, 1111} унарный, как и язык {1k | k является основной}. В класс сложности из всех таких языков иногда называют ВСЕГО.

Название «унарный» происходит от того факта, что унарный язык - это кодировка набора натуральные числа в унарная система счисления. Поскольку вселенная строк над любым конечным алфавитом является счетный набор, каждый язык может быть отображен в уникальный набор A натуральных чисел; таким образом, у каждого языка есть унарная версия {1k | k в}. И наоборот, каждый унарный язык имеет более компактную двоичную версию, набор двоичных кодировок натуральных чисел k так что 1k находится на языке.

Поскольку сложность обычно измеряется длиной входной строки, унарная версия языка может быть «проще», чем исходный язык. Например, если язык можно распознать за O (2п) времени, его унарную версию можно распознать за O (п) время, потому что п стал экспоненциально больше. В более общем смысле, если язык может быть распознан в O (f (п)) время и O (g (п)) пространство, его унарный вариант можно распознать в O (п + f (журнал п)) время и O (g (log п)) пространство (нам потребуется O (п) время просто прочитать входную строку). Однако, если членство на каком-либо языке неразрешимый, то членство в его унарной версии также неразрешимо.

Отношения с другими классами сложности

ВСЕГО содержится в П / поли- класс языков, которые можно распознать за полиномиальное время с помощью функции совета, которая зависит только от длины ввода. В этом случае необходимая функция совета очень проста - она ​​возвращает один бит для каждой длины ввода. k уточняя, является ли 1k на языке или нет.

Унарный язык обязательно скудный язык, поскольку для каждого п он содержит не более одного значения длины п и самое большее п значения длины не более п, но не все редкие языки унарны; таким образом ВСЕГО содержится в РЕДКО.

Считается, что нет NP-жесткий унарные языки: если существует унарный язык, НП-полный, тогда P = NP.[1]

Этот результат можно распространить на редкие языки.[2]

Если L это унарный язык, тогда L * (в Клини звезда из L) это обычный язык.[3]

Подсчет классов

Класс сложности P1 это класс унарных языков, которые могут быть распознаны машиной Тьюринга с полиномиальным временем (при условии, что ее входные данные записаны в унарном языке); это аналог класса п. Аналог НП в унарной установке - NP1. А счетный класс #П1, аналог #П, также известно.[4]

Рекомендации

Примечания

  1. ^ Петр Берман. Связь между плотностью и детерминированной сложностью NP-полных языков. В Материалы 5-й конференции по автоматам, языкам и программированию., стр.63–71. Springer-Verlag. Конспект лекций по информатике № 62. 1978.
  2. ^ С. Р. Махани. Редкие полные наборы для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25:130-143. 1982.
  3. ^ - Патрик. «Клини-звезда бесконечного унарного языка всегда дает регулярный язык». Обмен стеками информатики. Получено 19 октября 2014.CS1 maint: числовые имена: список авторов (связь)
  4. ^ Лесли Валиант, Сложность перечисления и проблемы надежности, [1] закрытый доступ

Общие ссылки