Барьеры и сложность монотонной цепи

Естественное доказательство является препятствием для доказательства нижних оценок сложности схемы булевых функций. Они напрямую не подразумевают такого барьера в доказательстве нижних границ сложности схемы. Есть ли прогресс в выявлении таких барьеров? Есть ли другие барьеры в монотонной обстановке?$monotone$

Недавняя статья Бенджамина Россмана суммирует современное состояние монотонной сложности схемы k-CLIQUE. Короче говоря, Разборов доказал нижнюю границу в 1985 году, позже улучшенную Алоном и Боппаной в 1987 году: , по сравнению с верхней границей грубой силы .$\omega(n^k/(\log n)^k)$$O(n^k)$

Россман показывает нижнюю границу для сложности среднего случая в модели случайных графов Эрдеша-Реньи; Амано ранее показал, что это, по сути, также верхняя граница. Квази-подсолнечная лемма, которая составляет ключевую часть статьи, довольно аккуратна.$\omega(n^{k/4})$

Таким образом, барьер естественных доказательств, кажется, не относится к монотонной сложности схемы.

Норберт Блум обсуждал, почему нижние оценки для монотонных цепей существенно отличаются от цепей с отрицаниями. Ключевым наблюдением Эвы Тардоса является то, что небольшая модификация тэта-функции Ловаша имеет экспоненциальную монотонную сложность схемы.

• Бенджамин Россман, Монотонная сложность k-Clique на случайных графах , FOCS 2010.
• Норберт Блум, Об отрицаниях в булевых сетях , LNCS 5760 , 18–29, 2009.
• É. Tardos . Разрыв между монотонной и немонотонной схемными сложностями является экспоненциальным , Combinatorica 8 , 141–142, 1987. doi: 10.1007 / BF02122563

Точка задается общей булевой функцией f, существует монотонная булева функция g, так что любая суперлинейная нижняя оценка g подразумевает единицу на f. Или сильнее общая сложность f равна монотонной сложности g до O (n).

Я до сих пор не уверен, как это связано с барьерами.