Нижние оценки пороговой функции

9

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

Теорема ( Патури ): Пустье быть любой непостоянной симметричной функцией, и обозначить еКзнак равное(Икс) когда |Икс|знак равноК (т.е. вес Хэмминга Икс является К). Примерная степенье, обозначается dег~(е), является Θ(N(N-Γ(е))), где Γ(е)знак равномин{|2К-N+1|:еКеК+1 а также 0КN-1}

Теперь пусть будет пороговой функцией, т.е. если . В этой статье (см. Раздел 8, стр. 15) говорится, что .TчасрT(Икс)TчасрT(Икс)знак равно1ИксTdег~(е)знак равно(T+1)(N-T+1)

Заметим, что для пороговой функции имеемпотому что когда функция меняется с 0 на 1. Я прав?Γ(TчасрT)знак равно|2(T-1)-N+1||Икс|знак равноT-1

Если я непосредственно применю теорему Патури к этому значению , я не получу нижнюю границу пороговой функции, о которой сообщалось в других статьях. Является ли значение выше верным? Что мне не хватает?ΓΓ(TчасрT)

Редактировать: я также пытался вычислить нижнюю границу квантового противника для порога. Сначала рассмотрим теорему.

Теорема (невзвешенный квантовый противник). Пусть - частичная булева функция, и пусть и - подмножество (жестких) входов. Пусть - отношение, и для каждого . Обозначим через минимальное число единиц в любой строке и любом столбце в отношении соответственно, а через обозначим максимальное число единиц в любой строке и столбце в любом из отношений соответственно. Тогда .еAе-1(0)Ве-1(1)рA×Врязнак равно{(Икс,Y)р:ИксяYя}1яNм,м'р,'ряQ2(е)знак равноΩ(мм'')

Если я определю как набор всех входов с числом 1, большим или равным , и всеми входами с 1s, строго меньшим , я получу (после некоторой алгебры), что .ВTATмм''знак равноN2пер(NT)пер(NN-T)

Так что я не получаю те же нижние границы, о которых сообщалось в других статьях. Теперь давайте сравним эти границы. На рисунке ниже показано для и без квадратных корней сравнение между оценкой теоремы Патури (синим цветом), оценкой противника (красным) и оценочной границей из других работ (зеленым).Nзнак равно200

введите описание изображения здесь

Мои вопросы:

1- Как я могу получить оценку в других статьях?

2. Из рисунка видно, что указанная нижняя граница (зеленая) также нижняя граница границы Патури и границы противника. Разве это не ослабляет «реальную» нижнюю границу? Например, если Патури говорит, что для всех симметричных функций у нас есть эта граница, то как вы можете получить соответствующую верхнюю границу для квантового счета ( )? Разве эта верхняя граница не нарушает теорему Патури?(T+1)(N-T+1)

Маркос Вильягра
источник
Вам не хватает абсолютного значения в расчете для (это кажется слишком маленьким изменением для редактирования). Γ(TчасрT)
Хартмут Клаук
Я думаю, что вы правы, и это своего рода приближение абсолютного значениячтобы получить степень, упомянутую в статье. Графики функций позволяют мне предположить, что :)Γ(TчасрT)знак равно|2(T-1)-N+1|
Марк Бери
да, это похоже на приближение (вот сюжет wolframalpha.com/input/… ). И это нижние границы . Если это так, то зачем это делать? Почему бы просто не применить полученную нижнюю границу от Патури? Γ(TчасрT)
Маркос Вильягра
1
Я полагаю, они хотят избежать функции абсолютного значения. Они получают более простую форму функции и избегают анализа в каждом конкретном случае для любого расчета. Мне интересно, как они получают это приближение из исходной функции?
Марк Бери
1
То же самое с точностью до константы.
Кристоффер Арнсфельт Хансен

Ответы:

6

Я не знаю, как вы можете получить или увидеть границу из оригинальной границы но вот доказательство того, что эти оценки асимптотически равны с точностью до постоянного множителя:(T+1)(N-T+1)n(N-|(2(T-1)-N+1|)

Сначала посмотрите, что (я исключаю потому что пороговая функция всегда равна ) Tзнак равно01

n(n|(2(t1)n+1|)={n(2t1)1tn/2+1/2n(2n2t+1)n/2+1/2tn1

Определите , и .f1(t)=n(2t1)f2(t)=N(2N-2T+1)г(T)знак равно(T+1)(N-T+1)

Теперь вы должны вычислить максимальное значение (согласно пределах определенных интервалов) фракций , , и . Вы можете сделать это с помощью дифференциального исчисления или аппроксимации с помощью графика (при достаточно большом ):Tе1(T)/г(T)е2(T)/г(T)г(T)/е1(T)г(T)/е2(T)N

f1(t)/g(t)f1(n/2+1/2)/g(n/2+1/2)n2n2/4=4

f2(t)/g(t)f2(n/2+1/2)/g(n/2+1/2)n2n2/4=4

g(t)/f1(t)g(1)/f1(1)знак равно2NNзнак равно2

г(T)/е2(T)г(N-1)/е2(N-1)знак равноN/2N/33/2

Это дает вам а также желаемый результат

n(n|2(t1)n1|)=Θ((t+1)(nt+1))
n(N-|2(T-1)-N-1|)знак равноΘ((T+1)(N-T+1)),

Есть ли более простой способ увидеть / получить этот результат?

Марк Бери
источник
1
Да, я думаю, что вы правы. У меня сложилось впечатление, что первоначальные авторы знали об этой нижней границе из-за некоторых результатов, таких как квантовое couting. В квантовой couting у нас есть верхняя граница , и, применяя теорему Патури и границы противника, они показали то, что вы только что показали здесь. (T+1)(N-T+1)
Маркос Вильягра
Спасибо за ваши старания!! Я думаю, что это ответ. Теперь я более убежден, что, возможно, это единственный способ получить такой результат.
Маркос Вильягра