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