Barreras y complejidad del circuito monótono

15

Las pruebas naturales son una barrera para probar los límites inferiores de la complejidad del circuito de las funciones booleanas. Ellos no implican directamente cualquier barrera en probar límites inferiores en el la complejidad del circuito. ¿Hay algún progreso hacia la identificación de tales barreras? ¿Existen otras barreras en el entorno monótono?monotone

Shiva Kintali
fuente
2
¿No escribió Dick Lipton una publicación sobre esto hace unos meses cuando hablaba de pruebas naturales? (actualización): aquí está el enlace: rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs
Suresh Venkat
44
Se conocen límites inferiores exponenciales en los circuitos monótonos (Razborov 85, Alon+Boppana 87).
Iddo Tzameret
2
¿Raz y McKenzie no separaron toda la jerarquía monótona de NC? (R. Raz, P. McKenzie, "Separación de la jerarquía monótona de NC")
Michaël Cadilhac
1
Una pregunta relacionada: cstheory.stackexchange.com/questions/2291/…
Gil Kalai
77
((¡No use para cursiva; use cursiva !))metrounth
Jeffε

Respuestas:

15

El reciente artículo de Benjamin Rossman resume el estado del arte de la complejidad del circuito monótono de k-CLIQUE. En resumen, Razborov demostró un límite inferior en 1985, luego mejorado por Alon y Boppana en 1987: , frente a la fuerza bruta O límite superior ( n k ) .ω(nortek/ /(Iniciar sesiónnorte)k)O(nortek)

Rossman muestra un límite inferior de para la complejidad del caso promedio en el modelo de gráficos aleatorios Erdős-Rényi; Amano demostró previamente que esto era esencialmente también el límite superior. El lema cuasi-girasol que forma una parte clave del papel es bastante limpio.ω(nortek/ /4 4)

Por lo tanto, la barrera de las pruebas naturales no parece aplicarse a la complejidad del circuito monótono.

Norbert Blum ha discutido por qué los límites inferiores para los circuitos monótonos son esencialmente diferentes de los circuitos con negaciones. La observación clave de Éva Tardos es que una pequeña modificación de la función theta de Lovász tiene una complejidad de circuito monótono exponencial.

András Salamon
fuente
1
También encontré que "Al probar los límites inferiores para el tamaño del circuito" de Karchmer es útil para comprender por qué los circuitos monótonos son diferentes de los circuitos con negación.
Kaveh
11

Al punto se le da una función booleana general f, hay una función booleana monótona g, de modo que cualquier límite inferior super lineal en g implica uno en f. O más fuerte, la complejidad general de f es igual a la complejidad monótona de g hasta O (n).

Todavía no estoy seguro de cómo se relaciona esto con las barreras.

Dick Lipton
fuente
18
Bienvenido a TCS SE !! Muchas gracias a las publicaciones de tu blog, ¡es realmente un placer leerlo!
Hsien-Chih Chang 張顯 之