Например, я знаю, что нерегулярный язык находится в A C 0 . Я хотел бы знать больше примеров, как это.
complexity-theory
regular-languages
circuits
Алекс Грило
источник
источник
Ответы:
Языки в могут быть более сложными, чем может предположить наивная интуиция.AC0
Мультиплексирование: находится в A C 0 .{ ш х : | ш | = 2N, | х | = n , w [ x ] = 1 } A C0
Мультиплексор это функция на переменных, которая выводит значение одной из 2 n переменных, где индекс определяется n переменными. (То же самое верно, если индекс написан в унарном формате.)2N+ n 2N N
Вычисление формул 3SAT производится в .A C0
Входные данные состоят из переменных, за которыми следуют несколько предложений, каждый из которых содержит три литерала, где каждый литерал представляет собой индекс переменной (унарный или двоичный, не имеет значения) и бит, указывающий на возможное отрицание. Вы можете оценивать литералы с помощью мультиплексоров, а затем добавить слой OR, а затем большой AND сверху.N
замкнуто относительно логических операций, конкатенации и композиции, таквы можете комбинировать выше примеров. Теперь вы должны чувствовать уважение к Р т я тA C0 и другим нижним границам цепи!пт я т у∉ С0
источник