Чувствительность-Блок Чувствительность Чувства - Последствия

12

Пусть - булева функция с чувствительностью s ( f ) и чувствительностью блока b s ( f ) .fs(f)bs(f)

Гипотеза о чувствительности блока чувствительности утверждает, что существует такое , что f , b s ( f ) s ( f ) c .c>0f, bs(f)s(f)c

Каковы значения правды и лжи этой гипотезы?

Пожалуйста, указывайте также ссылки.

Т ....
источник
2
Пожалуйста, подумайте над тем, чтобы сделать вопрос и его ответ более полезным, предоставив определения терминов «чувствительность» и «чувствительность блока».
Ян Йоханнсен
3
Предположение о чувствительности теперь доказано Хао Хуаном: arxiv.org/abs/1907.00847 .
Юваль
Гипотеза о чувствительности @YuvalFilmus следует как следствие. Так что, возможно, еще больше последствий.
T ....
c4

Ответы:

13

Вот что Скотт Ааронсон должен сказать по этому вопросу:

fffff

Проверка другой соответствующей литературы не дает никаких других убедительных последствий:

  • Нисан и Сегеди описывают вопрос, но не предлагают никакой мотивации.
  • Кеньон и Кутин упоминают, что это «естественный открытый вопрос».
  • Gotsman и Linial дают несколько надуманную эквивалентную проблему (гипотеза 5.33 на стр. 18 следующей статьи).
  • П. Хатами, Кулькарни и Панкратов в своем всеобъемлющем обзоре этой проблемы также не дают мотивации, но у них есть несколько эквивалентных формулировок. Например, гипотеза о чувствительности эквивалентна гипотезе о том, что сложность определения четности функции полиномиально ограничена чувствительностью. Гипотеза 5.31 на странице 17, из-за Ши, является одной переформулировкой, в которой вообще не упоминается чувствительность.
  • Амбайни, Баварский, Гао, Мао, Сунь и Зао утверждают, что гипотеза «берет свое начало в теории мер сложности булевых функций и сложности дерева решений», и в целом предлагают тот же тип мотивации, что и Скотт Ааронсон. Их недавний препринт - последнее слово в предположении (по состоянию на декабрь 2014 года).
Юваль Фильмус
источник
5

Ω(log(s(f)))fCREW(f)f

CREW(f)=Ω(logs(f))

CREW(f)

CREW(f)=Θ(logbs(f))

CREW(f)=O(logs(f))

CREW(f)

Денис Панкратов
источник