Sea la clase de los problemas de decisión que tienen un algoritmo aleatorio de error de dos lados limitado que se ejecuta en el tiempo .O ( f ( n ) )
¿Conocemos algún problema tal que pero ? ¿Está comprobada su inexistencia? Q ∈ B P T I M E ( n k ) Q ∉ D T I M E ( n k )
Esta pregunta se hizo en cs.SE aquí , pero no obtuvo una respuesta satisfactoria.
Respuestas:
Otro ejemplo es estimar el volumen de un poliedro en altas dimensiones. Hay un límite inferior incondicional en las estrategias deterministas para aproximar el volumen incluso a un factor exponencial, pero hay un FPRAS para el problema.
Actualización: el documento relevante es (enlace a PDF ):
I. Barany y Z. Furedi. Calcular el volumen es difícil, Geometría discreta y computacional 2 (1987), 319-326.
fuente
Problema : Una matriz consta de 1s y 0s. Encuentre una tal que sea 1.n n i A [ i ]A[1..2n] n n i A[i]
Se le permite consultar '¿Qué número está presente en '? Cada consulta lleva tiempo constante.A[i]
Solución : Algoritmo aleatorizado: elija un índice aleatorio y compruebe si es 1. El número esperado de consultas es 2, pero cualquier algoritmo determinista debe realizar al menos consultas. Por lo tanto, el límite superior aleatorizado es estrictamente mejor que el límite inferior determinista en este modelo.A [ i ] ni A[i] n
Este es un ejemplo de la complejidad de la consulta a la que Tsuyoshi se refería en el comentario.
fuente
Vea también Algoritmos aleatorios eficientes y simples donde el determinismo es difícil .
fuente