Какие нерегулярные языки в

11

Например, я знаю, что нерегулярный язык находится в A C 0 . Я хотел бы знать больше примеров, как это.aNбNAС0

Алекс Грило
источник
Палиндромы ( ){wwR}
Вор
Что такое C 0 ? AC0
vonbrand
@vonbrand, - класс цепей постоянной глубины, содержащий и / или затворы неограниченного разветвления. То есть каждый вентиль в цепи является либо вентилем «и», либо «или», и допускает поступление неограниченного числа входов.AС0
Николас Манкузо

Ответы:

9

Языки в могут быть более сложными, чем может предположить наивная интуиция.AC0

  • Очевидно, что содержит { a n b n c n } , который не является контекстно-свободным.AC0{anbncn}
  • Каждый унарный язык находится в неоднородном ; например, проблема остановки, выраженная в одинарных.AC0
  • Сложение может быть реализовано в с помощью суммирующего переносчика. Здесь вход представляет собой 2 n битов, представляющих два числа, а выход содержит n + 1 провод (эквивалентно, каждый выходной бит может быть реализован в A C 0 )AC02nn+1AC0
  • Мультиплексирование: находится в A C 0 .{весИкс:|вес|знак равно2N,|Икс|знак равноN,вес[Икс]знак равно1}AС0

    Мультиплексор это функция на переменных, которая выводит значение одной из 2 n переменных, где индекс определяется n переменными. (То же самое верно, если индекс написан в унарном формате.)2N+N2NN

  • Вычисление формул 3SAT производится в .AС0

    Входные данные состоят из переменных, за которыми следуют несколько предложений, каждый из которых содержит три литерала, где каждый литерал представляет собой индекс переменной (унарный или двоичный, не имеет значения) и бит, указывающий на возможное отрицание. Вы можете оценивать литералы с помощью мультиплексоров, а затем добавить слой OR, а затем большой AND сверху.N

  • не содержит большинство, но она содержит приблизительное большинство: функциюкоторая равна большинствоесли выход1AС0нули или единицы. См. «Примерный подсчет с равномерными цепями постоянной глубины» от Ajtai.12+ε

замкнуто относительно логических операций, конкатенации и композиции, таквы можете комбинировать выше примеров. Теперь вы должны чувствовать уважение к Р т я тAС0 и другим нижним границам цепи!пaряTYAС0

sdcvvc
источник
У вас есть ссылки на это? Особенно эта унарная проблема остановки в . Так как A C 0A C = N C P , я не понимаю этого (уже поздно, где я, это может быть моим оправданием). AС0AС0AСзнак равноNСп
Пол GD
1
AС0п/поLY
@ PålGD, она выложена в Arora и Barak текста.
Николас Манкузо
У вас есть ссылка для доказательства того, что мультиплексирование в AC0?
Алекс Грило
1
@ Алекс Грило, к сожалению, нет; Я думаю, что это фольклор. Просто сделайте . язнак равно02N-1(Иксзнак равноявес[я]знак равно1)
sdcvvc