Función aleatoria monótono

15

En el documento de Pruebas naturales de Razborov-Rudich , página 6, en la parte que discuten que hay "fuertes pruebas de límites inferiores contra modelos de circuito monótono " y cómo encajan en la imagen, están las siguientes oraciones:

Aquí el problema no es la constructividad, las propiedades utilizadas en estas pruebas son factibles, sino que parece no haber un buen análogo formal de la condición de amplitud. En particular, nadie ha formulado una definición viable de una "función monótona aleatoria".

¿No es fácil distinguir las salidas de una función monótona de una cadena aleatoria? ¿No nos dice la existencia de límites inferiores fuertes que no existen tales cosas?

Mi pregunta es:

¿Qué quieren decir con una definición viable de una "función monótona aleatoria" ?

Kaveh
fuente
2
Una pregunta relacionada: cstheory.stackexchange.com/questions/1484/…
Gil Kalai
No estoy seguro de lo que tenían en mente. En realidad, existe una forma muy natural de definir funciones de corte monótonas aleatorias. también el artículo de rossman sobre la complejidad monótona de k-clique en gráficos aleatorios usa gráficos erdos-renyi que en realidad también son bastante naturales. tenga en cuenta que el papel de pruebas naturales tiene más de 1.5 décadas de antigüedad ahora.
vzn

Respuestas:

12

No estoy seguro, pero creo que el problema aquí es el hecho de que no tenemos suposiciones sólidas sobre los generadores de funciones monótonas pseudoaleatorias (al menos ninguna que yo sepa). La idea de la prueba en el documento de Razborov-Rudich es la siguiente:

Si existe una propiedad natural de las funciones (es decir, una propiedad decidible de manera eficiente que se mantiene para un subconjunto de funciones suficientemente grande e implica que la función necesita grandes circuitos), entonces se puede usar para romper los generadores de funciones pseudoaleatorios (que también rompe los generadores pseudoaleatorios y uno funciones de ruta).

Si tuviéramos que reformular el teorema en términos de funciones monótonas y circuitos monótonos, nos gustaría que dijera

Si existe una propiedad natural de las funciones monótonas (es decir, una propiedad decidible de manera eficiente que se mantiene para un subconjunto suficientemente grande de funciones monótonas e implica que la función necesita grandes circuitos monótonos ), entonces se puede usar para romper los generadores de funciones pseudoaleatorios (que también rompe pseudoaleatorio generadores y funciones unidireccionales),

pero ahora la prueba del documento deja de funcionar, porque nuestro generador pseudoaleatorio genera funciones generales, no necesariamente monótonas, y no podemos usar nuestra propiedad natural para romperlo, porque incluso un subconjunto relativamente grande de funciones monótonas no será grande en relación con funciones generales, para el conjunto de funciones monótonas en sí no es grande en relación con el conjunto de todas las funciones ( http://en.wikipedia.org/wiki/Dedekind_number ). Podríamos definir algún generador de funciones monótonas pseudoaleatorias y usar la propiedad natural para romperlo, pero probablemente no tendríamos la equivalencia entre este generador y las funciones unidireccionales, por lo que el teorema no sería tan interesante.

Tal vez esta dificultad se pueda solucionar (pero no creo que se deduzca de la prueba en el documento de una manera directa) y tal vez el problema con las funciones monótonas se encuentre en otro lugar. Realmente me gustaría que alguien más experimentado que yo confirme mi respuesta o muestre dónde estoy equivocado.

Karolina Sołtys
fuente