Монотонная сложность вычислительных функций на разреженных входах

Вес $|x|$ двоичной строки $x\in\{0,1\}^n$ - количество единиц в строке. Что произойдет, если мы заинтересованы в вычислении монотонной функции на входах с несколькими из них?

Мы знаем, что решить, имеет ли граф клик, сложно для монотонных цепей (см., Среди прочего, Alon Boppana, 1987), но если граф имеет, например, не более ребер, можно найти монотонную ограниченную схему глубины размера которая решает -клик. $k$ $k^3$ $f(k)\cdot n^{O(1)}$ $k$

Мой вопрос: есть ли какая-либо функция, которую трудно вычислить с помощью монотонной схемы даже на входах с весом меньше ? Здесь жесткий означает размер цепи . $k$ $n^{{k}^{\Omega(1)}}$

Еще лучше: существует ли явная монотонная функция, которую трудно вычислить, даже если мы заботимся только о входных значениях веса и ? $k_1$ $k_2$

Эмиль Йержабек уже заметил, что известные нижние оценки имеют место для монотонных схем, которые разделяют два класса входных данных ( -cliques против максимальных -цветных графов), таким образом, за счет некоторой независимости в вероятностном аргументе можно сделать это работа для двух классов ввода фиксированного веса. Это приведет к тому, что будет функцией которую я хочу избежать. $a$ $(a-1)$ $k_2$ $n$

Что действительно хотелось бы, так это явная жесткая функция для $k_1$ и $k_2$ намного меньшая, чем $n$ (как в параметризованной структуре сложности). Еще лучше, если $k_1=k_2+1$ .

Обратите внимание, что положительный ответ для $k_1=k_2$ будет означать экспоненциальную нижнюю оценку для произвольных цепей.

Обновление : этот вопрос может быть частично актуальным.

cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone MassimoLauria
источник

На ваш самый первый (общий) вопрос (не о Клике). Я думаю, что даже случай с входами не более

очень сложен. Возьмем двудольный

граф

. Присвойте каждой вершине

булеву переменную

. Пусть

монотонная булева функция, минтермы являются

для ребер

из

. Пусть

2

$2$

n \times m

$n\times m$

G

$G$

m = o (n)

$m=o(n)$

u

$u$

x_{u}

$x_u$

f_{G} (x)

$f_G(x)$

x_{u} \land x_{v}

$x_u\land x_v$

u v

$uv$

G

$G$

минимальный размер монотонной схемы, которая правильно вычисляет

на входах с

. Тогда любая нижняя оценка

для константы

будет означатьэкспоненциальнуюнижнюю оценку длянемонотонныхцепей.

s (G)

$s(G)$

f_{G}

$f_G$

\leq 2

$\leq 2$

s (G) \geq (2 + c) n

$s(G)\geq (2+c)n$

c > 0

$c>0$

Стасис

≫ n / 2

$\gg n/2$

\exp (min {a, n / b}^{1 / 4})

$\exp(\min\{a,n/b\}^{1/4})$

b

$b$

a

$a$

a < b

$a<b$

k

$k$

n^{k}

$n^k$

k \geq 3

$k\geq 3$

(n - k)

$(n-k)$

O (n^{2} \log n)

$O(n^2\log n)$ для каждой константы .

k

$k$

Стасис

Я должен уточнить, что я забочусь о разреженных входах в смысле разреженного графика. Поиск клика в очень разреженном графе (с, скажем, ребрами) может быть выполнен в монотонной схеме FPT.

k

$k$

k^{10}

$k^{10}$

MassimoLauria

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

k

$k$

k

$k$

MassimoLauria

Мой первый комментарий основывался на сложности графика. Феномен " " можно найти на странице 13 этого проекта . Кстати, я не совсем понял, что вы имеете в виду, говоря, что "тяжело для k и k + 1"? (Моя вина, конечно.)

(2 + c) n

$(2+c)n$

Стасис

В частности, рассматривая одну часть вопроса (например, для = 1, = 2), Локам изучил функции «2-среза» в этой статье и доказывает, что сильные нижние оценки для них могут быть обобщены, поэтому это очень сложная открытая задача. связанные с разделением классов базовой сложности, и любая такая конструкция / явная функция была бы прорывом; из аннотации: $k_1$ $k_2$

Булева функция f называется двухслойной функцией, если она оценивается как ноль на входах с менее чем двумя единицами и оценивается как единица на входах с более чем двумя единицами. На входах с ровно двумя единицами f может быть нетривиально определено. Существует естественное соответствие между 2-слайс-функциями и графиками. Используя структуру сложности графов, мы показываем, что достаточно сильные суперлинейные монотонные нижние оценки для очень специального класса 2-срезовых функций будут означать суперполиномиальные нижние оценки по полному базису для некоторых функций, полученных из них.

Сложность графа и функции срезов / Сатьянараяна В. Локам, Теория вычислений. Systems 36, 71–88 (2003)

также, как и в своих комментариях, SJ освещает этот аналогичный случай в своей книге в разделе, посвященном изучению сложности звезд в графах, раздел 1.7.2.

Сложность булевой функции: достижения и границы , Стасис Юкна

ВЗН
источник

Монотонная сложность вычислительных функций на разреженных входах

Ответы: