Circuito monótono de la complejidad de las funciones informáticas en entradas dispersas

El peso $|x|$ de una cadena binaria $x\in\{0,1\}^n$ es el número de unos en la cadena. ¿Qué sucede si estamos interesados en calcular una función monótona en entradas con pocas?

Sabemos que decidir si un gráfico tiene una $k$ -clique es difícil para los circuitos monótonos (ver, entre otros, Alon Boppana, 1987), pero si un gráfico tiene, por ejemplo, a lo sumo $k^3$ bordes, es posible encontrar un circuito monotono de profundidad limitada $f(k)\cdot n^{O(1)}$ que decide $k$ -clique.

Mi pregunta: ¿hay alguna función que sea difícil de calcular por un circuito monótono incluso en entradas de peso inferior a $k$ ? Aquí duro significa tamaño de circuito $n^{{k}^{\Omega(1)}}$ .

Aún mejor: ¿existe una función monótona explícita que sea difícil de calcular incluso si solo nos interesan las entradas de peso $k_1$ y $k_2$ ?

Emil Jeřábek ya observó que los límites inferiores conocidos se mantienen para los circuitos monótonos que separan dos clases de entradas ( gráficas $a$ cliques versus maximal $(a-1)$ -coloreable), por lo que a costa de cierta independencia en el argumento probabilístico es posible hacerlo trabajar para dos clases de entrada de peso fijo. Esto causaría que $k_2$ sea una función de $n$ que quiero evitar.

Lo que es realmente me gustaría es una función explícita duro para $k_1$ y $k_2$ mucho menor que $n$ (como en el marco de la complejidad parametrizado). Aún mejor si $k_1=k_2+1$ .

Observe que una respuesta positiva para $k_1=k_2$ implicaría un límite inferior exponencial para circuitos arbitrarios.

Actualización : esta pregunta puede ser parcialmente relevante.

cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone MassimoLauria
fuente

A su primera pregunta (general) (no sobre Clique). Creo que incluso el caso de las entradas con un máximo de

unidades es muy difícil. Tome una gráfica bipartita

con

. Asigne a cada vértice

una variable booleana

. Deje

sea una función booleana monótona cuyos términos mínimos son

para los bordes

. Sea

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$

sea el tamaño mínimo de un circuito monótono que calcula correctamente

en entradas con

unidades. Entonces, cualquier límite inferior

para una constante

implicaría unlímite inferiorexponencialparacircuitosno monótonos.

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$

Stasys

≫ 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)$ para cada constante .

k

$k$

Stasys

Debo aclarar que me importan las entradas dispersas en el sentido de un gráfico disperso. La búsqueda de una -clique en un gráfico muy escaso (con digamos bordes) se puede hacer en un tamaño de circuito monótono FPT.

k

$k$

k^{10}

$k^{10}$

MassimoLauria

Su ejemplo en el primer comentario es muy agradable. Si entiendo correctamente, este es un problema similar con las funciones monótonas que son difíciles en un peso fijo . Usando funciones de pseudocomplemento para simular entradas negadas, la complejidad del circuito no difiere entre casos monótonos y no monótonos. Para constante (o pequeña), este pseudocomplemento puede implementarse eficientemente mediante un circuito monótono.

k

$k$

k

$k$

MassimoLauria

Mi primer comentario se basó en la complejidad del gráfico. El fenómeno " " se puede encontrar en la página 13 de este borrador . Por cierto, no he entendido bien lo que quieres decir con "difícil para k y k + 1"? (Mi culpa, por supuesto.)

(2 + c) n

$(2+c)n$

Stasys

considerando específicamente una parte de la pregunta (por ejemplo, para = 1, = 2), Lokam estudió las funciones de "2 cortes" en este documento y demuestra que los límites inferiores fuertes en ellas pueden generalizarse, por lo tanto, este es un problema muy difícil de abrir relacionado con la separación de clases de complejidad básica y cualquier construcción / función explícita sería un gran avance; del resumen: $k_1$ $k_2$

Una función booleana f se denomina función de 2 divisiones si se evalúa a cero en las entradas con menos de dos 1 y se evalúa como una en las entradas con más de dos 1. En entradas con exactamente dos 1's, f puede definirse de manera no trivial. Existe una correspondencia natural entre las funciones de 2 divisiones y los gráficos. Usando el marco de la complejidad del gráfico, mostramos que los límites inferiores monótonos superlineales suficientemente fuertes para la clase muy especial de funciones de 2 cortes implicarían límites inferiores superpolinomiales sobre una base completa para ciertas funciones derivadas de ellos.

Complejidad gráfica y funciones de corte / Satyanarayana V. Lokam, Theory Comput. Sistemas 36, 71–88 (2003)

también como en sus comentarios, SJ cubre este caso similar en su libro en la sección que explora la complejidad estelar de los gráficos, sección 1.7.2.

Complejidad de la función booleana: avances y fronteras , Stasys Jukna

vzn
fuente

Circuito monótono de la complejidad de las funciones informáticas en entradas dispersas

Respuestas: