В сложности дерева решений для булевой функции очень хорошо известный метод нижней границы состоит в том, чтобы найти (приблизительный) многочлен, который представляет функцию. Патури дал характеристику для симметричных булевых (частичных и полных) функций в терминах величины, обозначаемой :
Теорема ( Патури ): Пусть быть любой непостоянной симметричной функцией, и обозначить когда (т.е. вес Хэмминга является ). Примерная степень, обозначается , является , где
Теперь пусть будет пороговой функцией, т.е. если . В этой статье (см. Раздел 8, стр. 15) говорится, что .
Заметим, что для пороговой функции имеемпотому что когда функция меняется с 0 на 1. Я прав?
Если я непосредственно применю теорему Патури к этому значению , я не получу нижнюю границу пороговой функции, о которой сообщалось в других статьях. Является ли значение выше верным? Что мне не хватает?
Редактировать: я также пытался вычислить нижнюю границу квантового противника для порога. Сначала рассмотрим теорему.
Теорема (невзвешенный квантовый противник). Пусть - частичная булева функция, и пусть и - подмножество (жестких) входов. Пусть - отношение, и для каждого . Обозначим через минимальное число единиц в любой строке и любом столбце в отношении соответственно, а через обозначим максимальное число единиц в любой строке и столбце в любом из отношений соответственно. Тогда .
Если я определю как набор всех входов с числом 1, большим или равным , и всеми входами с 1s, строго меньшим , я получу (после некоторой алгебры), что .
Так что я не получаю те же нижние границы, о которых сообщалось в других статьях. Теперь давайте сравним эти границы. На рисунке ниже показано для и без квадратных корней сравнение между оценкой теоремы Патури (синим цветом), оценкой противника (красным) и оценочной границей из других работ (зеленым).
Мои вопросы:
1- Как я могу получить оценку в других статьях?
2. Из рисунка видно, что указанная нижняя граница (зеленая) также нижняя граница границы Патури и границы противника. Разве это не ослабляет «реальную» нижнюю границу? Например, если Патури говорит, что для всех симметричных функций у нас есть эта граница, то как вы можете получить соответствующую верхнюю границу для квантового счета ( )? Разве эта верхняя граница не нарушает теорему Патури?
Ответы:
Я не знаю, как вы можете получить или увидеть границу из оригинальной границы но вот доказательство того, что эти оценки асимптотически равны с точностью до постоянного множителя:( t + 1 ) ( n - t + 1 )--------------√ n ( n - | ( 2 ( т - 1)−n+1|)−−−−−−−−−−----------√
Сначала посмотрите, что (я исключаю потому что пороговая функция всегда равна )т = 0 1
Определите , и .f1(t)=n(2t−1) f2( t ) = n ( 2 n - 2 t + 1) г( t ) = ( t + 1 ) ( n - t + 1 )
Теперь вы должны вычислить максимальное значение (согласно пределах определенных интервалов) фракций , , и . Вы можете сделать это с помощью дифференциального исчисления или аппроксимации с помощью графика (при достаточно большом ):T е1( т ) / г( т ) е2( т ) / г( т ) г( т ) /е1( т ) г( т ) /е2( т ) N
Это дает вам а также желаемый результат
Есть ли более простой способ увидеть / получить этот результат?
источник