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

42

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

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

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

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

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

  • A C A C CNC ( , ) Иерархия ACACC

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

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

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

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

хазисоп
источник
2
Это очень похоже на вопрос сообщества Wiki. Должен ли я преобразовать это?
Дейв Кларк,
Теорема Ладнер можно обобщить , чтобы получить бесконечные иерархии между другими классами (при условии , что они различны) , например, между Р и Р ^ # Р .
Тайсон Уильямс
13
Можно также упомянуть теоремы об «антииерархии», то есть теоремы о дихотомии. Теоремы о дихотомии, вероятно, могли бы получить полный обзор самих себя, но, вероятно, их следует хотя бы упомянуть наряду с чем-то вроде теоремы Ладнера.
Джошуа Грохов
1
Вы спрашиваете только об иерархиях классов задач? Существует также понятие «иерархия тестов», см. , Например , arxiv.org/abs/quant-ph/0308032 .
Алессандро Косентино
1
Да, рассматриваются только иерархии классов сложности. Даже если их ограничить, существует достаточно много информации для сбора.
Chazisop

Ответы:

21

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

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

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

Открытая проблема - показать, что иерархия Фурье бесконечна по отношению к оракулу (то есть строго содержится в ).FHkFHk+1

Робин Котари
источник
18

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

Теорема. Для любой итоговой вычислимой функции такой, что , существует итоговая вычислимая такой, что . f ( n ) = Ω ( n ) g : NN T I M E [ g ( n ) ] = T I M E [ f ( g ( n ) ) ]f:NNf(n)=Ω(n)g:NNTIME[g(n)]=TIME[f(g(n))]

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

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

TIME[nk]i.o.TIME[nk1]/(nlogn)

(существуют проблемы во времени, когда не может быть успешно решен с помощью машины времени использующей советов, даже для всего бесконечного количества входных длин). Доказательство легко: позвольте перечислить машин времени, которые принимают битов советов в качестве второго входа. Определите который разбивает на где, запускает и выдает противоположный ответ. Тогда .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 . о . - Т Я Мnknk1nlogn{Mi}nk1nlognM(x)xx=yz|z|=log|x|Mz(x,y)L(M)i.o.TIME[nk1]/(nlogn)

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

Райан Уильямс
источник
2
Это ? в противном случае утверждение не интересно: просто выберите . g ( n ) = nTIME[g(n)]=TIME[f(g(n))]g(n)=n
Сашо Николов
@ Сашо, похоже, так. Утверждение теоремы Бородина о разрыве (по ссылке) говорит о многом.
Даниэль Апон
16

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

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

  • C0P=P
  • C1P=PP
  • Ck+1P=PPCkP

Затем, что касается полиномиальной иерархии, определяется как .CHkCkP

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

[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.

Bruno
источник
16

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

Также на ECCC .

Йонатан
источник
здесь показано, что большинство свойств требуют запросов в квантовой модели. Это может быть включено в доказательство теоремы об иерархии ответа, чтобы показать, что оно справедливо и для проверки квантовых свойств. (Фактически для любой естественной вычислительной модели, имеющей хотя бы одно свойство, для тестирования которого требуются запросы , и любой вычислимой вас есть свойства, которые можно проверить в запросов). Ω ( g ( n ) ) f ( n ) O ( g ( n ) ) Θ ( f ( n ) )Ω(n)Ω(g(n))f(n)O(g(n))Θ(f(n))
Артем Казнатчеев
11

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

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

Существует класс , определенный в статье 1975 года Л. Адельманом и К. Мандерсом, который является диофантовым аналогом класса . Язык содержится в если существует такой многочлен , что Является ли равным является открытой проблемой. Это равенство показало бы связь между теорией чисел и информатикой.DNPLDP

xLy1,yn<poly(|x|): P(x,y1,,yn)=0.
DNP

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

i1, ΣiDΣiPΣi+1D
Александр Кноп
источник
Вы имеете в виду doi.ieeecomputersociety.org/10.1109/SFCS.1975.9 или doi.ieeecomputersociety.org/10.1109/SFCS.1976.13 ?
Андрас Саламон
D определяется во втором («Диофантова сложность»).
GMB
@ AndrásSalamon Ссылки не работают.
8

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

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

Андраш Саламон
источник
8

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

  • A -иерархия
  • AW -hierarchy
  • EW -иерархия
  • LOG -иерархия
  • M -иерархия
  • S -иерархия
  • W -иерархия
  • Wfunc -иерархия

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

Martin Lackner
источник
5

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

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

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

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

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

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

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

оборота дкупер
источник
4

В сложности пропозиционального доказательства есть иерархии, подобные иерархическим сложностям. Например, пропозициональные системы крыш аналогичны , системы доказательства C-Фреге для аналогичны классам сложности схем и т. Д.P H C P CGiPHCPC

Существуют также иерархии в ограниченной арифметике, например, теории и т. Д.Sji

Кава
источник
4

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

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

Маркос Вильягра
источник
3

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

Климент С.
источник
Указатель на этот ответ , который фокусируется на первом (GoldreichKNR09).
Клемент С.
3

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

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

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

Тайфун Пей
источник
1

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

Денис Панкратов
источник
Спасибо за добавление, я отредактировал ваш комментарий, чтобы прояснить, что coNP относится к сложности коммуникации (я знаю, что это обычно отбрасывается в сообществе сложности коммуникации, чтобы избежать беспорядка обозначений).
chazisop
1

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

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

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

оборота user3483902
источник
0

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

Макс Кубершки
источник