У всех классов сложности есть характеристика языка листа?

Листовые языки - прекрасный способ единообразно определить множество классов сложности. Большинство классов сложности обычно определяются моделью вычисления (например, детерминированной / рандомизированной ТМ) и привязкой к ресурсу (время журнала, поли-пространство и т. Д.). Однако в формулировке конечного языка существует только одна модель вычислений, и класс задается путем предоставления его конечного языка.

Детали слишком длинные, чтобы объяснять, поэтому я направлю заинтересованных читателей на любой из этих двух опросов:

Единообразные характеристики классов сложности по Х. Фоллмеру
Листовые языковые занятия К.В. Вагнера

Оба опроса делают большую работу по объяснению формулировки на первых нескольких страницах.

В обзоре Вагнера он говорит: «Оказывается, что практически каждый класс сложности, который до сих пор рассматривался, может быть описан языками-листами».

Мой вопрос относится к этому утверждению. Я знаю, что есть некоторые классы, для которых мы не знаем характеристику конечного языка, так что это означает, что либо классы не обязательно имеют такую характеристику, либо мы не нашли ее.

Ожидаем ли мы, что каждый класс сложности (скажем, между P и PSPACE) будет иметь характеристику конечного языка? (Давайте ограничимся «естественными» классами сложности.) Есть ли какой-либо результат такого рода в литературе?

(Смежный вопрос, на который я был бы рад узнать ответ: есть ли (эвристический) метод, чтобы придумать листовой язык для данного класса?)

РЕДАКТИРОВАТЬ: Суреш указывает, что в статье Википедии есть краткое определение лиственных языков. Я копирую это ниже.

Несколько классов сложности обычно определяются в терминах недетерминированной машины Тьюринга за полиномиальное время, где каждая ветвь может принимать или отклонять, а вся машина принимает или отклоняет как некоторую функцию от условий ветвей. Например, недетерминированная машина Тьюринга принимает, если принимает хотя бы одна ветвь, и отклоняет только если отклоняют все ветви. Со-недетерминированная машина Тьюринга, с другой стороны, принимает, только если все ветви принимают, и отклоняет, если отклоняет любая ветвь. Многие классы могут быть определены таким образом.

cc.complexity-theory complexity-classes Робин Котари
источник

В Википедии есть довольно лаконичное определение языка листа: может быть, вы можете приспособить это к вопросу?

Суреш Венкат

Благодарю. Я не знал, что в Википедии есть статья об этом. Я скопировал их определение в конце моего вопроса.

Робин Котари

Посмотри на

Бернд Борхерт, Риккардо Сильвестри: характеристика листовых языковых классов. Inf. Процесс. Lett. 63 (3): 153-158 (1997) ( ссылка здесь )

Авторы характеризуют листовые языковые классы как классы, которые являются (a) «исчисляемыми», (b) являются «нисходящими» замкнутыми по многим временам сводимостью многие-один, и (c) «объединенными замкнутыми» (то есть непересекающимися объединениями) по многим временам многозначность

$L$ $C,D \in L$ $E \leq^P_m C \sqcup D$ $E \in L$ $\sqcup$

$P/poly$ $SPACE[n]$ $SPACE[n] \neq P$ $SPACE[n]$ не закрывается при таких сокращениях.)

Райан Уильямс
источник

Отлично. Это то, что мне было нужно. (Есть идеи, как найти такую характеристику, зная, что она существует? Может быть, даже эвристика, а не то, что всегда работает?)

Робин Котари

В этом случае у меня сложилось впечатление, что авторы построили на основе известных результатов вида «все листовые языки имеют свойство X» и «ни один листовой язык не обладает свойством Y», и нашли прямой способ связать все это, добавив только правильные условия.

Райан Уильямс

У всех классов сложности есть характеристика языка листа?

Ответы: