Hay una multitud de problemas para los cuales podemos probar límites inferiores en la complejidad Y tener algoritmos que demuestren que estos límites son ajustados:
- Todos los algoritmos de búsqueda y clasificación sin clasificar de tiempo lineal, ya que estos necesariamente requieren examinar cada pieza de datos.
- La comparación de tiempo lineal lineal, como lo demuestra fácilmente un simple argumento teórico de la información.
- Ciertos algoritmos de geometría computacional de tiempo linealítmico (como el casco convexo y el árbol de expansión mínima euclidiana) por reducción a la clasificación.
También hay problemas para los que tenemos límites inferiores, pero no podemos probar que sean ajustados, porque no tenemos algoritmos que cumplan estos límites. El mejor ejemplo que sé es:
- La multiplicación de matrices es al menos [matemática] o (n ^ 2) [/ matemática]. Algunos creen que esto es un límite estrecho, pero nuestro mejor algoritmo hasta la fecha es solo [matemática] O (n ^ {2.3728639}) [/ matemática]
Creo que puede haber problemas similares con respecto a la complejidad de la comunicación en la computación cuántica, pero no estoy familiarizado con los detalles.
- ¿Qué significa el símbolo # en esta pregunta matemática?
- ¿Hay ramas de las matemáticas y las ciencias que no se han descubierto, o hemos agotado todo el conocimiento que requerimos sobre estos dos?
- ¿Cuáles son las aplicaciones prácticas de las colas con doble terminación?
- ¿Qué es una función de punto fijo y cuándo son útiles?
- ¿Podríamos usar la definición de integración de suma de Riemann para obtener las integrales de cualquier función polinómica o trascendental?
