Какие иерархии и / или теоремы иерархии вы знаете?

В настоящее время я пишу обзор теорем иерархии на TCS. В поисках соответствующих статей я заметил, что иерархия является фундаментальной концепцией не только в TCS и математике, но и во многих науках, от теологии и социологии до биологии и химии. Видя, что объем информации огромен, я надеюсь, что смогу попросить помощи у этого сообщества. Конечно, я не хочу, чтобы вы проводили для меня библиографический поиск, а скорее я прошу два вида информации:

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

2. Иерархии и теоремы об иерархиях, которые вы считаете абсолютно необходимыми для включения в опрос такого рода. Это, вероятно, мне уже известно, но было бы полезно увидеть, какие иерархии вы считаете более важными и почему. Это может быть что-то типа «Я считаю, что очень важен, потому что без него мы не смогли бы проводить такого рода исследования» или «Хотя это не так хорошо известно, в TCS на основе логики мы постоянно используем эту иерархию, и я считаю, это важный инструмент. " , И да, я верю, что у людей из логики есть много иерархий, которые нужно упомянуть, однако имейте в виду, что мы говорим об иерархиях проблем.$PH$

Я буду держать обновленный список здесь:

• $DTIME$ Иерархия
• $NTIME$ Иерархия
• $SPACE$ Иерархия
• Арифметическая (также известная как Клини) Иерархия
• Гиперарифметическая иерархия
• Аналитическая Иерархия
• Хомская Иерархия
• Иерархия Гжегорчика и связанные с ней: иерархия Вайнера (быстро растущая), иерархия Харди
  (медленно растущая) и иерархия Веблена
• Иерархия ричи
• Иерархия Axt (как определено в Axt63 )

• Иерархия петель (определена в MR67 )

• A C A C $NC$ ( , ) Иерархия $AC$$ACC$

• Иерархия глубины, как определено в Sipser83
• Полиномиальная иерархия ( ) и менее изощренная иерархия Мейера-Стокмейера (нет различий между квантификаторами)$PH$
• Экспоненциальная иерархия ( )$ELEMENTARY$

• $NP$ Промежуточная иерархия (теорема Ладнера)

• Не очень крепкий (Артур-Мерлин)$AM$

• (Недетерминированный Fixed-параметры) иерархия и связанная с ним Переменным Вт иерархия ( -hierarchy) и -hierarchy (Вт с зависящей от параметра Глубина)A W W $W$$AW$$W^{*}$
• Иерархия счета
• Иерархия Фурье
• Булева иерархия (более ), также равная иерархии запросов (более )Н $NP$$NP$
• Иерархии для тестирования свойств, как видно из GoldreichKNR09
• Точечная иерархия беззвездных регулярных языков
• $BP_{d}(P)$ : классы, решаемые программами ветвления полиномиального размера, с дополнительным условием, что каждый бит ввода проверяется не более d раз, образуют иерархию для различных значений$d$
• Временная иерархия для сложности цепей
• Полиномиальная иерархия в сложности коммуникации

Примечание. Если вы не хотите, чтобы вас упоминали исключительно, скажите об этом. Как правило, я упомяну как сообщество, так и конкретного человека, который выявляет новую информацию.

Иерархия Фурье, как определено в « Яоюнь Ши, Квантовые и классические компромиссы ».

Из сложности зоопарка :

$\mathsf{FH}_k$ - это класс задач, решаемых однородным семейством квантовых цепей полиномиального размера, где уровней вентилей Адамара и всех других вентилей сохраняют вычислительный базис.$k$

• $\mathsf{FH}_0 = \mathsf{P}$
• $\mathsf{FH}_1 = \mathsf{BPP}$
• $\mathsf{FH}_2$ содержит факторинг из-за алгоритма оценки фазы Китаева .

Открытая проблема - показать, что иерархия Фурье бесконечна по отношению к оракулу (то есть строго содержится в ).$\mathsf{FH}_k$$\mathsf{FH}_{k+1}$

- Наряду с «антииерархиями» стоит упомянуть теорему Бородина о разрыве .

Теорема. Для любой итоговой вычислимой функции такой, что , существует итоговая вычислимая такой, что . f ( n ) = Ω ( n ) g : N → N T I M E [ g ( n ) ] = T I M E [ f ( g ( n ) ) $f : {\mathbb N} \rightarrow {\mathbb N}$$f(n) = \Omega(n)$$g : {\mathbb N} \rightarrow {\mathbb N}$${\sf TIME}[g(n)] = {\sf TIME}[f(g(n))]$

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

- Есть также интересные укрепления обычных временных иерархий, такие как:

(существуют проблемы во времени, когда не может быть успешно решен с помощью машины времени использующей советов, даже для всего бесконечного количества входных длин). Доказательство легко: позвольте перечислить машин времени, которые принимают битов советов в качестве второго входа. Определите который разбивает на где, запускает и выдает противоположный ответ. Тогда .n k - 1 n - log n { M i } n k - 1 n - log n M ′ ( x ) x x = y z | z | = журнал | х | M z ( x , y ) L ( M ′ ) ∉ i . о . - Т Я $n^k$$n^{k-1}$$n-\log n$$\{M_i\}$$n^{k-1}$$n-\log n$$M'(x)$$x$$x=yz$$|z|=\log |x|$$M_z(x,y)$$L(M') \notin i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$

- Отсутствие известных временных иерархий в определенных ситуациях следует рассматривать (как открытые проблемы). Например, является ли ?${\sf BPTIME}[n] = {\sf BPP}$

Сложность зоопарк дает вам некоторые иерархии . Среди них Иерархия Счетов и Булева Иерархия еще не упоминались.

[РЕДАКТИРОВАТЬ] Чтобы сделать мой ответ более информативным, быстрое определение счетной иерархии.

• ${\sf C_0P} = {\sf P}$
• ${\sf C_1P} = {\sf PP}$
• ${\sf C_{k+1}P} = {\sf PP^{C_kP}}$

Затем, что касается полиномиальной иерархии, определяется как .$\sf CH$$\bigcup_k {\sf C_kP}$

Иерархия счета была определена Вагнером [Wag86]. Связи с теорией пороговых цепей были обнаружены Allender & Wagner [AW93]. Совсем недавно Бюргиссер [Bür09] также использовал счетную иерархию, чтобы связать модель Валианта с гипотезой Шуба и Смейла. В частности, он доказал, что гипотеза подразумевает суперполиномиальную нижнюю оценку перманента.$\tau$$\tau$

[Wag86] К.В. Вагнер. Сложность комбинаторных задач с кратким входным представлением . Acta Mathematica 23 (3), 325-356, 1986.
[AW93] E. Allender & KW Wagner. Подсчет иерархий: полиномиальное время и схемы постоянной глубины . Современные тенденции в области компьютерных наук , 469-483, 1993.
[Bür09] P. Bürgisser. Об определении целых чисел и доказательстве нижней границы арифметической схемы . Вычислительная сложность 18 (1), 81-103, 2009.

Goldreich et. и др. иметь теоремы иерархии для тестирования свойств:

• Одед Голдрайх, Михаил Кривелевич, Илан Ньюман, Эяль Розенберг: теоремы иерархии для проверки свойств. Тестирование собственности , Конспект лекций в области компьютерных наук, Vol. 6390, с. 289-294, Springer, 2010.

Также на ECCC .

Sipser показал иерархию глубины в , то есть, что цепи глубины размера poly более мощны, чем цепи глубины размера poly: d + 1 $AC^0$$d+1$$d$

Сипсер М. Борелевские множества и сложность схем . СТОК 1983.

Дитер Ван Мелкебек и соавторы имеют иерархию времени и пространства для семантических моделей с рекомендациями, включая рандомизацию.

• Дитер ван Мелкебек, Константин Первышев: общая временная иерархия с одним советом . Вычислительная сложность 16 (2): 139-179 (2007)
• Джефф Кинн, Дитер ван Мелкебек: Результаты пространственной иерархии для рандомизированных и других семантических моделей . Вычислительная сложность 19 (3): 423-475 (2010)

Вот больше иерархий для семантических классов с советами. В частности, для ZPTIME и RTIME.

Лэнс Фортноу, Рахул Сантанам, Лука Тревизан. Иерархии для семантических выражений . В STOC'05.

Существует иерархия Чжэн-Вейхрауха для действительных чисел

X. Zheng и K. Weihrauch. Арифметическая иерархия действительных чисел . Математическая логика ежеквартально. 47 (2001), № 1 51 - 65.

Существует класс , определенный в статье 1975 года Л. Адельманом и К. Мандерсом, который является диофантовым аналогом класса . Язык содержится в если существует такой многочлен , что Является ли равным является открытой проблемой. Это равенство показало бы связь между теорией чисел и информатикой.$\mathsf{D}$$\mathsf{NP}$$L$$\mathsf{D}$$P$

Существует диофантовый аналог полиномиальной иерархии, называемый «диофантовой иерархией». Полиномиальная и диофантовая иерархии взаимосвязаны:

Другая строгая иерархия: ветвящиеся программы, которые проверяют каждый бит ограниченное количество раз. Чем больше тестов разрешено, тем больше класс ветвящихся программ. Обычно программы ветвления также ограничены полиномиальным размером. BP _d (P) - это класс программ разветвления полиномиального размера, которые могут проверять каждый бит до раз.$d$

L / poly - это объединение BP _d (P) по всем d , а BP _d-1 (P) BP _d (P) для каждого d .$\subsetneq$

В теории параметризованной сложности существует несколько иерархий, хотя в публикациях часто встречается только упомянутая -иерархия. Другие являются:$\mathsf{W}$

• $\mathsf{A}$ -иерархия
• $\mathsf{AW}$ -hierarchy
• $\mathsf{EW}$ -иерархия
• $\mathsf{LOG}$ -иерархия
• $\mathsf{M}$ -иерархия
• $\mathsf{S}$ -иерархия
• $\mathsf{W^∗}$ -иерархия
• $\mathsf{W^{func}}$ -иерархия

Все они описаны в теории параметризованной сложности, Flum и Grohe, Birkhäuser, 2006 .

Не уверен, что это соответствует вашим критериям, но есть иерархия точек-глубин регулярных языков без звездочек.

Иерархия для размера цепи, см. Предыдущий вопрос .

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

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

Каждый автомат четности имеет ранг где и , описывающий структуру условия принятия. Поэтому, если язык распознается автоматом (det / ND / alt) ранга мы говорим, что принадлежит -уровню (соответственно):i ∈ { 0 , 1 } i ≤ j L [ i , j ] L [ i , j $[i,j]$$i\in\{0,1\}$$i\leq j$$L$$[i,j]$$L$$[i,j]$

• детерминистская иерархия Мостовского (не все обычные языки)
• недетерминированная мостовская иерархия
• чередующаяся мостовская иерархия

Уровень знакопеременной иерархии (т. определяется как по Бючи, так и по ко-Бючи) соответствует слабому уровню и характеризуется слабыми знакопеременными автоматами, которые порождают иерархию:$\Sigma_2\cap \Pi_2$$L$

• слабая иерархия индексов (не все обычные языки)

Для всех этих иерархий (кроме детерминированной) разрешимость членства в уровне для данного регулярного языка является открытой проблемой. Связи между этими иерархиями и топологическими классификациями (также называемыми иерархией Ваджа и иерархией Бореля) также создали несколько открытых проблем. Например, предполагается, что слабая иерархия индекса и борелевская иерархия совпадают. Известно, что все эти иерархии являются строгими, и в последнее время были решены некоторые особые случаи определения уровня (особенно низких уровней или с помощью входного детерминированного автомата).$L$

В сложности пропозиционального доказательства есть иерархии, подобные иерархическим сложностям. Например, пропозициональные системы крыш аналогичны , системы доказательства C-Фреге для аналогичны классам сложности схем и т. Д.P H C ⊂ P$G_i$$\mathsf{PH}$$C \subset \mathsf{P}$$C$

Существуют также иерархии в ограниченной арифметике, например, теории и т. Д.$\mathsf{S^i_j}$

Вот новая иерархия для контекстно-свободных языков от Tomoyuki Yamakami.

Он вводит механизм оракула в недетерминированных автоматах с понижением, а также понятия Тьюринга и сводимости «многие один». Затем создается новая иерархия для контекстно-свободных языков (CFL), аналогичная полиномиальной иерархии. Например, , и т. Д. Интересная часть всего этого заключается в том, что коллапс в иерархии CFL происходит тогда и только тогда, когда рушится иерархия полиномов.C F L C F $CFL$$CFL^{CFL}$

Разработка одного из пунктов, упомянутых в OP (GoldreichKNR09): существует несколько теорем иерархии в тестировании свойств и доказательств близости, касающихся сложности запроса, адаптивности или тестируемости в отношении количества раундов (для доказательств близость). Смотрите, например,

• Теоремы об иерархии для проверки свойств , Одед Голдрайх, Михаил Кривелевич, Илан Ньюман и Эял Розенберг, 2012. https://link.springer.com/article/10.1007/s00037-011-0022-4 [упомянуто ОП]
• Теорема об иерархии для интерактивных доказательств близости , Том Гур и Рон Ротблюм, 2017. http://drops.dagstuhl.de/opus/volltexte/2017/8153/
• Теоремы об иерархии для проверки свойств в запутанном запросе сложности , Одед Голдрайх, 2018. https://eccc.weizmann.ac.il/report/2018/098/
• Теорема об адаптивной иерархии для тестирования свойств , Clément Canonne и Tom Gur, 2018. https://link.springer.com/article/10.1007%2Fs00037-018-0168-4

Из этого вопроса о cs.stackexchange я узнал об иерархии рода обычных языков . По сути, вы можете охарактеризовать обычные языки на основе минимальной поверхности рода, в которую может быть встроен график их DFA. В [1] показано, что существуют языки произвольно большого рода и что эта иерархия правильная.

1. Бонфанте, Гийом и Флориан Делуп. « Род регулярных языков». Математические структуры в информатике 28.1 (2018): 14-44.

Считая полиномиальную иерархию, #PH для краткости. Первый уровень - #P, затем #NP ... и т. Д.

Полиномиальная иерархия в сложности коммуникации, как определено Бабаем, Франком и Саймоном (см. Оригинальную статью здесь и без платной информации здесь ). Значение этой иерархии трудно переоценить. Прежде всего, функция дизъюнктивности была введена BFS в той же статье, в которой была представлена ​​иерархия, а дизъюнктивность вполне естественно возникла как задача coNP -полная. Как вы знаете, дизъюнктность является функцией в коммуникационной сложности. Во-вторых, доказательство нижних границ полиномиальной иерархии в сложности коммуникации является основной открытой проблемой с важными последствиями в других областях TCS (например, см. Эту статью и ссылки в ней).$^{cc}$

Рассмотрим Однозначную Полиномиальную Иерархию, ссылку здесь , оригинальную ссылку здесь для однозначной Полиномиальной Иерархии (Paywalled). При изучении булевой иерархии BH и таких классов, как которые имеют хорошие результаты, связанные с замыканием, и устанавливают различия, мы можем исследовать связи с однозначными вычислениями. $D_{p}$

Как утверждают авторы (в оригинальной ссылке), классы и дают результаты, связанные с и . При однозначной схеме они могли бы характеризовать разному. Кроме того, с вышеуказанной иерархией связана однозначная иерархия обещаний. Результаты Lowness для Однозначной Полиномиальной Иерархии - «если для установлен разреженный Завершитель Тьюринга , иерархия падает до более низких уровней или в Однозначный Случай Обещания». $NC^{k}$$AC^{k}$$P$$PSPACE$$P$$UP$

Для дальнейшего изучения булевых связок и изоморфизма графов относятся Низкая и Высокая Иерархии , также ссылка на Википедию .

Еще немного о неясной стороне: моя теорема об иерархии второго порядка для логики с неподвижной точкой в ​​теории конечных моделей. См. Еще одну теорему об иерархии .