В теории вычислительной сложности унарный язык или язык подсчета — это формальный язык (набор строк ), где все строки имеют вид 1 k , где «1» может быть любым фиксированным символом. Например, язык {1, 111, 1111} является унарным, как и язык {1 k | k is prime }. Класс сложности всех таких языков иногда называется 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 — классе языков, которые могут быть распознаны за полиномиальное время с помощью функции advice, зависящей только от длины входных данных. В этом случае требуемая функция advice очень проста — она возвращает один бит для каждой длины входных данных 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]
