Существуют ли неконструктивные доказательства существования «маленьких» машин Тьюринга / NFA?

11

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

Формально:

предположим, нам дан некоторый язык и исправим некоторую вычислительную модель (NFA / машина Тьюринга / и т. д.).LΣ*

Существуют ли какие-либо неконструктивные результаты существования, показывающие, что состояние машины для существует, но без возможности найти (в время) это?L p o l y ( n , | Σ | )NLпоLY(N,|Σ|)

Например, есть ли регулярный язык для которого мы можем показать но мы не знаем, как построить автомат с состояниями?n s c ( L ) n nLNsс(L)NN

( - это недетерминированная сложность состояний , т. е. количество состояний в минимальной NFA, которая принимает ).L LNsс(L)LL


РЕДАКТИРОВАТЬ: после некоторого обсуждения с Марцио (спасибо!) Я думаю, что я мог бы лучше сформулировать вопрос следующим образом:

Существует ли язык и вычислительная модель, для которой выполняется следующее:L

  1. Мы знаем, как построить машину, которая вычисляет с состояниями.мLм

  2. У нас есть доказательство того, что существует состояние машины для (где ), но либо мы вообще не можем ее найти, либо потребовалось бы экспоненциальное время для ее вычисления.Nп < < мLN<<м

RB
источник
что такое NSC (L)? кажется, вопрос связан со сложностью сжатия / Колмогорова, которая требует найти маленькие (est) машины для представления строк ...
vzn
nsc (L) - это недетерминированная сложность состояний L (количество состояний в наименьшем NFA, который принимает L).
РБ
другая идея / ракурс, может быть, есть какие-то "маленькие" классы схем (другая вычислительная модель), для которых доказано, что они могут вычислять определенные функции, но фактическая конструкция хитрая? SJ недавно упомянул Баррингтона, что разветвленные программы шириной 5 могут вычислять большинство ...?
ВЗН
@vzn Доказательство теоремы Баррингтона дает простую процедуру преобразования формул в программы ветвления.
Сашо Николов
1
@RB: хорошо, вы можете найти более интересные примеры из ограниченной по Колмогорову сложности (в частности, ограниченной по времени сложности). Например, если задана строка , какая наименьшая машина работает за время O ( 2 n ) и печатает x ? В этом случае мы можем легко построить TM, который печатает x , но для нахождения самого маленького требуется сканировать все TM | М | < | х | (ограничение по времени делает его вычислимым). Когда у меня будет больше времени, я расширю свой ответ. ИксО(2N)ИксИкс|M|<|Икс|
Марцио Де Биаси

Ответы:

8

Только расширенный комментарий с тривиальным примером; Вы можете выбрать одноэлементный язык:

LКзнак равно{M|σ(M)знак равноΣ(К)}

т.е. содержит первую (в лексикографическом порядке) занятую бобра машину Тьюринга размера k (машина Тьюринга размера k, которая достигает наибольшего числа 1 на своей ленте после остановки).LККК

Для каждого язык L k является регулярным ... но мы не знаем, как построить небольшой DFA, который его распознает (хотя он имеет только 2 k ( log k + 2 ) состояний) :-)КLК2*К(журналК+2)

Марцио де Биаси
источник
Хотя я согласен, что это работает, я искал методы показа существования для явно заданного языка L.
RB
3
Что такое «явно заданный язык»?
Джефф
3

Язык (для некоторого простого числа p ) может быть распознан квантовыми конечными автоматами с ограниченной ошибкой (QFA) с O ( log p ) -состоянием, но доказательство не является конструктивный.MОDпзнак равно{aяп|я0}пО(журналп)

Наиболее известным конструктивно полученным числом состояний является для QFA с ограниченной ошибкой, распознающих M O D p .О(журнал2+о(1)п)MОDп

REF: раздел 4.2 (Ambainis и Yakaryilmaz, 2015) .

Абузер Якарылмаз
источник
2

Другое решение заключается в использовании леммы Хигмана :

Язык, закрытый по подсловам, является регулярным.

UvUv

Итак, возьмем любой язык L, его подсловное слово регулярно, но совсем не конструктивно, так как L произвольно.

CP
источник