После прочтения соответствующего вопроса о неконструктивных доказательствах существования алгоритмов мне стало интересно, есть ли способы показать существование «маленьких» (скажем, состояний) вычислительных машин без фактического их построения.
Формально:
предположим, нам дан некоторый язык и исправим некоторую вычислительную модель (NFA / машина Тьюринга / и т. д.).
Существуют ли какие-либо неконструктивные результаты существования, показывающие, что состояние машины для существует, но без возможности найти (в время) это?L p o l y ( n , | Σ | )
Например, есть ли регулярный язык для которого мы можем показать но мы не знаем, как построить автомат с состояниями?n s c ( L ) ≤ n n
( - это недетерминированная сложность состояний , т. е. количество состояний в минимальной NFA, которая принимает ).L L
РЕДАКТИРОВАТЬ: после некоторого обсуждения с Марцио (спасибо!) Я думаю, что я мог бы лучше сформулировать вопрос следующим образом:
Существует ли язык и вычислительная модель, для которой выполняется следующее:
Мы знаем, как построить машину, которая вычисляет с состояниями.м
У нас есть доказательство того, что существует состояние машины для (где ), но либо мы вообще не можем ее найти, либо потребовалось бы экспоненциальное время для ее вычисления.п < < м
Ответы:
Только расширенный комментарий с тривиальным примером; Вы можете выбрать одноэлементный язык:
т.е. содержит первую (в лексикографическом порядке) занятую бобра машину Тьюринга размера k (машина Тьюринга размера k, которая достигает наибольшего числа 1 на своей ленте после остановки).LК К К
Для каждого язык L k является регулярным ... но мы не знаем, как построить небольшой DFA, который его распознает (хотя он имеет только ≤ 2 ∗ k ( log k + 2 ) состояний) :-)К LК ≤ 2 ∗ k ( logк + 2 )
источник
Язык (для некоторого простого числа p ) может быть распознан квантовыми конечными автоматами с ограниченной ошибкой (QFA) с O ( log p ) -состоянием, но доказательство не является конструктивный.М О Дп= { ая п∣ i ≥ 0 } п O ( журналр )
Наиболее известным конструктивно полученным числом состояний является для QFA с ограниченной ошибкой, распознающих M O D p .O ( журнал2 + о ( 1 )р ) М О Дп
REF: раздел 4.2 (Ambainis и Yakaryilmaz, 2015) .
источник
Другое решение заключается в использовании леммы Хигмана :
Итак, возьмем любой язык L, его подсловное слово регулярно, но совсем не конструктивно, так как L произвольно.
источник