Точная сложность проблемы в

9

Позволять xi{1,0,+1} за i{1,,n}с обещанием, что x=i=1nxi{0,1} (где сумма закончилась Z). Тогда какова сложность определения, еслиx=1?

Обратите внимание, что тривиально проблема заключается в m2AC0[m] потому что x1modmесли . Вопрос в том, заключается ли проблема в ? Если так, то что за схема свидетельствует об этом? Если нет, то как это доказать?x=1AC0

SamiD
источник
Эта проблема вполне может быть тривиальной, но я не знаю ответа и был бы очень заинтересован в ее знании.
Самид

Ответы:

7

Вы можете использовать обычный аргумент переключения леммы. Вы не объяснили, как вы представляете свои входные данные в двоичном формате, но при любой разумной кодировке следующая функция AC -эквивалентна вашей функции: (мы предполагаем, что четное.) Следуя этим примечаниям к лекции , предположим, что можно вычислить с помощью схемы глубины размера . Тогда случайное ограничение входов оставляет функцию сложности дерева решений не более0

f(x1,,xn)={0if x1x2+x3x4+xn=0,1if x1x2+x3x4+xn=1,?otherwise.
nfdnbnn1/2d2d(b+1)+1 с вероятностью не менее . Расчет, вероятно, покажет, что это еще один экземпляр (с меньшим входным размером) с вероятностью , и поэтому существует некоторое случайное ограничение, которое выдает оба экземпляра на входов и функция с постоянной сложностью дерева решений, приводящая к противоречию. Тот же аргумент должен давать экспоненциальные нижние оценки.11/(3n)fΘ(1/n)fn1/2d
Юваль Фильмус
источник
Я думаю, что общая чувствительность этой функции также будет , так что вы, вероятно, могли бы использовать это, чтобы получить экспоненциальную нижнюю границу в моем ответе. Приведенный здесь результат использует теорему Линиала-Мансура-Нисана, которая сама использует лемму о переключении + простые оценки спектра функций с низкой сложностью дерева решений. Θ(n)
Сашо Николов
7

Я не думаю, что это в AC0, и я могу показать нижнюю границу для связанной задачи обещания различения между и , когда . Подобные методы Фурье должны применяться к вашей проблеме, но я не проверял это. Или, может быть, есть простое сокращение.xi=0xi=2x{1,1}n

Предположим, что существует схема глубины размера , которая вычисляет функцию такую, что всякий раз, когда . Потому что для случайного вероятность того, что равна , и для каждого такого существует координаты, которые меняют значение , общее влияние равноsdf:{1,1}n{0,1}f(x)=ixiixi{0,2}xixi=02n(nn/2)n1/2xn/2ffΩ(n1/2), что примерно так же, как большинство (потому что вы включили большинство чувствительных входных данных большинства). По теореме Хастада (см. Colorraly 2.5 в заметках Райана О'Доннела ) это означает, что

s2Ω(n1/(2d2)).
Сашо Николов
источник