Este es un seguimiento de la respuesta de Suresh. Como él dice, hay muchos problemas de construcción en geometría computacional donde la complejidad de la salida es un límite inferior trivial en el tiempo de ejecución de cualquier algoritmo. Por ejemplo: los arreglos de líneas planas, los diagramas tridimensionales de Voronoi y los gráficos de visibilidad plana tienen complejidad combinatoria en el peor de los casos, por lo que cualquier algoritmo que construya esos objetos trivialmente requiere Ω ( n 2 ) en el peor de los casos. . (Existen algoritmos de tiempo O ( n 2 ) para los tres problemas).Θ(n2)Ω(n2)O ( n2)
Pero también se conjetura que se aplican restricciones similares a los problemas de decisión . Por ejemplo, dado un conjunto de n líneas en el plano, ¿con qué facilidad puede verificar si tres líneas pasan por un punto común? Bueno, podrías construir la disposición de las líneas (el gráfico plano definido por sus puntos de intersección y los segmentos entre ellas), pero eso lleva tiempo . Uno de los principales resultados de mi tesis doctoral fue que dentro de un modelo de cálculo de árbol de decisión restringido pero natural, se requiere un tiempo Ω ( n 2 ) para detectar intersecciones triples. Intuitivamente, debemos enumerar todosΘ ( n2)Ω ( n2)( n2) puntos de intersección y busque duplicados.
Del mismo modo, hay un conjunto de números donde triples de elementos suman cero. Por lo tanto, cualquier algoritmo (modelada por una cierta clase de árboles de decisión) para probar si un determinado conjunto contiene tres elementos que suman cero requiere el tiempo . (Es posible eliminar algunos registros a través del paralelismo a nivel de bits, pero lo que sea).Θ ( n2)Ω ( n2)
Otro ejemplo, también de mi tesis, es el problema de Hopcroft: dados puntos y líneas en el plano, ¿algún punto contiene alguna línea? Se sabe que el número de incidentes en el peor de los casos es . Probé que en un modelo de cómputo restringido (pero aún natural), se requiere tiempo para determinar si hay incluso una incidencia de línea de punto. Intuitivamente, debemos enumerar todas las incidencias cercanas de y verificar cada una para ver si realmente es una incidencia.nortenorteΘ ( n4 / 3)Ω ( n4 / 3)Θ ( n4 / 3)
Formalmente, estos límites inferiores siguen siendo solo conjeturas, porque requieren modelos restringidos de cómputo, que se especializan en el problema en cuestión, especialmente para el problema de Hopcroft). Sin embargo, probar límites más bajos para estos problemas en el modelo de RAM probablemente sea tan difícil como cualquier otro problema de límite inferior (es decir, no tenemos idea): vea el documento SODA 2010 de Patrascu y Williams que relaciona las generalizaciones de 3SUM con el tiempo exponencial hipótesis.