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

12

El peso |x|de una cadena binaria x{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 k3 bordes, es posible encontrar un circuito monotono de profundidad limitada f(k)nO(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 nkΩ(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 k1 y k2 ?

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 (a1) -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 k2 sea ​​una función de n que quiero evitar.

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

Observe que una respuesta positiva para k1=k2 implicaría un límite inferior exponencial para circuitos arbitrarios.

Actualización : esta pregunta puede ser parcialmente relevante.

MassimoLauria
fuente
2
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 n × m G con m = o ( n ) . Asigne a cada vértice u una variable booleana x u . Deje f G ( x ) sea una función booleana monótona cuyos términos mínimos son x ux v para los bordes u v de G . Sea s ( G2n×mGm=o(n)uxufG(x)xuxvuvG sea ​​el tamaño mínimo de un circuito monótono que calcula correctamente f G en entradas con2 unidades. Entonces, cualquier límite inferior s ( G ) ( 2 + c ) n para una constante c > 0 implicaría unlímite inferiorexponencialparacircuitosno monótonos. s(G)fG2s(G)(2+c)nc>0
Stasys
1
n/2b una un < b k n k k 3 ( n - k ) O ( n 2 log n ) kexp(min{a,n/b}1/4)baa<bknkk3(nk)O(n2logn) para cada constante . 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 10kk10
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. kkk
MassimoLauria
2
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
Stasys

Respuestas:

2

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 2k1k2

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.

vzn
fuente