Caracterización de problemas para los que existen algoritmos de tiempo sublineales.

Me preguntaba si los problemas para los cuales existen algoritmos de tiempo sublineal (en el tamaño de entrada) pueden caracterizarse por poseer propiedades específicas. Esto incluye el tiempo sublineal (por ejemplo, pruebas de propiedad, una noción alternativa de aproximación para problemas de decisión), espacio sublinear (por ejemplo, algoritmos de boceto / transmisión en los que la máquina Turing tiene una cinta de solo lectura, un espacio de trabajo sublineal y una salida de solo escritura cinta) y mediciones sublineales (p. ej., recuperación dispersa / detección de compresión). En particular, estoy interesado en tal caracterización tanto para el marco de los algoritmos de prueba de propiedad como para el modelo clásico de algoritmos aleatorios y de aproximación.

Por ejemplo, los problemas para los que existe una solución de programación dinámica exhiben una subestructura óptima y subproblemas superpuestos; aquellos para los que existe una solución codiciosa exhiben una subestructura óptima y la estructura de un matroide. Y así. Cualquier referencia relacionada con este tema es bienvenida.

Con la excepción de algunos problemas que admiten un algoritmo sub lineal lineal determinista, casi todos los algoritmos sublineales que he visto son aleatorios. ¿Existe alguna clase de complejidad específica relacionada con los problemas que admiten algoritmos de tiempo sublineales? En caso afirmativo, ¿se incluye esta clase en BPP o PCP?

cc.complexity-theory ds.algorithms complexity-classes approximation-algorithms Massimo Cafaro
fuente

tiempo sub-lineal en qué modelo?

Kaveh

Los algoritmos de prueba de propiedad están en el marco general de lo que desea, pero primero debe responder el punto de Kaveh.

Suresh Venkat

He editado mi pregunta agregando la información solicitada.

Massimo Cafaro

La Transformada de Fourier de un vector se puede calcular en tiempo sublineal cuando es (casi)

dispersa en el dominio de la frecuencia. Entonces la propiedad aquí es escasa. Verifique, por ejemplo, "Algoritmo simple y práctico para la transformación de Fourier dispersa" de Haitham Hassanieh, Piotr Indyk, Dina Katabi y Eric Price nms.lcs.mit.edu/~dina/pub/soda12.pdf y referencias allí.

k

$k$

Dimitris

Respuestas:

Para la tarea de tiempo constante de probar las propiedades del gráfico, se conoce una caracterización interesante. Una propiedad de gráfico es una función de todos los gráficos a , y una propiedad de gráfico es comprobable si hay un algoritmo aleatorio tal que para todos y todos los gráficos : $\{0,1\}$ $P$ $A$ $\varepsilon > 0$ $G$

lee solo losbordes de para alguna función $A(G)$ $g(\varepsilon)$ $G$ $g$
Si entonces salidas `` Sí '' con alta probabilidad (por ejemplo, al menos ) $P(G)=1$ $A(G)$ $2/3$
Si se deben agregar o eliminar al menos bordes de para obtener un tal que (es decir, es lejos de la propiedad ), entonces genera `` no '' con una probabilidad de al menos $\varepsilon n^2$ $G$ $G'$ $P(G')=1$ $G$ $\varepsilon$ $A(G)$ $2/3$

Esto es, puede distinguir entre gráficos que tienen y gráficos que tienen alta distancia de edición de gráficos que tienen . Alon, Fischer, Newman y Shapira demostraron que una propiedad es comprobable de esta manera si y solo si la propiedad se puede "reducir" a la propiedad de verificar si un gráfico tiene una partición regular (en el sentido de Szemeredi) . Esto muestra que la regularidad de las pruebas es "completa" para las pruebas, en cierto sentido. (También hay una versión de prueba de error unilateral, consulte la referencia). $A$ $P$ $P$ $P$ $\varepsilon$

Ryan Williams
fuente

En el ámbito del espacio sublineal , no hay una clase explícita de problemas que admitan una solución de espacio sublinear, pero hay grandes clases de problemas (estimación de momento de frecuencia, reducción de dimensionalidad, etc.) donde se puede mostrar la existencia de un pequeño "boceto" y esto conduce a algoritmos eficientes.

Pero también en este espacio, todos los algoritmos son aleatorios, y existen fuertes límites inferiores deterministas basados principalmente en la complejidad de la comunicación.

Suresh Venkat
fuente