Complejidad de espacio de casos promedio

11

Estoy tratando de encontrar problemas cuya complejidad de espacio de casos promedio ha sido analizada.

Más específicamente, estoy interesado en saber si hay algún problema con un límite inferior de complejidad espacial comprobada que sea superlineal, y especialmente si hay alguno con un análisis de caso promedio (por ejemplo, el límite se mantiene incluso si el algoritmo está permitido errar por un pequeño porcentaje de veces, etc.)

Gracias por adelantado

cc.complexity-theory reference-request space-bounded average-case-complexity usuario4359
fuente
2
Si pudiera ser más específico, creo que será más probable que obtenga respuestas a su pregunta. Por "complejidad de espacio de caso promedio" de un problema, ¿quiere decir el promedio del espacio mínimo requerido para resolver cada conjunto de instancias de algún problema? No estoy seguro de que esté bien definido, aunque no es algo en lo que haya pensado con gran detalle. Si quiere decir algo más simple, como la complejidad espacial promedio de un algoritmo particular al resolver un problema, entonces creo que su pregunta podría no obtener muchas respuestas porque hay muchas posibilidades. (continúa en el siguiente comentario)
jbapple
(continúa desde arriba) En particular, si eso es lo que quiere decir, su pregunta podría ser demasiado general para TCS SE: cstheory.stackexchange.com/faq Quizás, quizás no. El primer ejemplo que me viene a la cabeza es ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , pero muchas estructuras de datos aleatorios tienen análisis de espacio.
jbapple
3
@jbapple: No puedo seguir tu crítica. Pensé que era claro a partir de la pregunta que el autor de la pregunta está buscando trabajos en la contraparte de complejidad espacial de la complejidad de tiempo promedio de caso de Levin, y aún así lo creo incluso después de leer sus comentarios. No puedo responder la pregunta no porque la pregunta no sea clara, sino porque no conozco bien el tema y no conozco tal trabajo.
Tsuyoshi Ito
@ Tsuyoshi Ito: Tienes razón.
jbapple
interpretar "análisis de caso promedio" como "el algoritmo puede equivocarse varias veces" hace que parezca un análisis aleatorio.
Suresh Venkat

Respuestas:

7

Estoy interesado pero no estoy familiarizado con este tema. Buscando "Teoría de la complejidad de casos promedio", encontré una tesis escrita por Tomoyuki Yamakami:

Teoría de la complejidad computacional del caso promedio , Tomoyuki Yamakami, 1997.

La Sección 3.5.1 parece relevante, se define una noción análoga al espacio similar a la complejidad del tiempo promedio. Esperemos que con una lectura más profunda encontremos algunos problemas que han sido analizados :)

También en el periódico

Sobre la teoría de la complejidad de los casos promedio , Shai Ben-David, Benny Chor, Oded Goldreich y Michael Luby, 1989.

La complejidad promedio del espacio logarítmico se define en la Sección 7.

Hsien-Chih Chang 張顯 之
fuente