Малые цепи для задачи оценки цепи

14

Пусть будет функцией, которая отображает схему s- гейта C на n битов и n- битную строку x на C ( x ) . Предположим, что схемы кодируются как ациклическая последовательность назначений k : = g ( i , j ), где i , j , k - метки проводов.СярсUяTЕvaLs,NsСNNИксС(Икс)Кзнак равнограмм(я,J)я,J,К

Я знаю, что это немного забавный вопрос, но какова самая известная верхняя граница сложности схемы этой проблемы? Существует одноленточных ТМ, вычисляющих эту функцию, и поэтому при моделировании Фишера-Пиппенгера должно быть достаточно размера O ( ( s + n ) 2 log ( s + n ) ) . Квадратика возникает из-за необходимости искать назад и вперед. Можно ли сделать лучше? Можно ли это сделать в размере O ( s + n ) ?О((s+N)2)О((s+N)2журнал(s+N))О(s+N)

Исаак Меклер
источник

Ответы:

16

Из разговора с Райаном Уильямсом (который заслуживает похвалы за мою возможность опубликовать этот ответ) я узнал, что от Пола и Пиппенджера известно, что Circuit Eval может быть решена квазилинейным временным мультитейпом ТМ, а также что есть сокращения от мультитейпа TM для цепей, которые дают только квазилинейный размер. То есть Circuit Eval имеет схемы размером , согласно вашей формулировке.(N+s)журналО(1)(N+s)

Это доказательство приведено здесь, на странице 6 (см. Теорему 3.1 (Фольклор)).

Дилан Маккей
источник
Это прекрасно, спасибо! И спасибо Райану!
Исаак Меклер