Oh chico. Los límites inferiores en la dificultad del problema son una de las cosas más difíciles en toda la informática. Mucho más difícil que esa pequeña pregunta fácil de P =? NP de la que quizás hayas oído hablar. Esencialmente, todavía no tenemos idea de cómo demostrar que un problema es difícil.
El TL, DR responde a su pregunta:
- No, no hay forma conocida de que funcione en general.
- Sí, hay algunos casos especiales: algunos algoritmos para los cuales podemos hacer tal prueba.
- En la práctica, usted sabe que su algoritmo es óptimo porque es obvio, o no tenemos idea de cómo demostrar su optimización.
Ahora con más detalle.
¿Por qué los límites inferiores son tan difíciles? Para demostrar que un problema es fácil , solo necesita encontrar un algoritmo específico que lo resuelva de manera eficiente. Para demostrar que un problema es difícil, debe demostrar que ninguno de los infinitos algoritmos posibles puede resolverlo de manera eficiente. Y eso no se puede hacer un algoritmo a la vez. En cambio, debe encontrar alguna propiedad inherente del problema que lo dificulte. ¿Cómo encontrar tales propiedades? A excepción de algunos casos especiales bastante triviales, nadie lo sabe.
- Cuando se computa con exponentes muy grandes (> 150) con un número entero pequeño, ¿es mejor utilizar la aritmética de precisión arbitraria o la exponenciación modular?
- Cómo averiguar qué castillo conectar con qué otro, para que los caminos sean los menos largos
- ¿Cuál es la diferencia entre 802.11, a / b / g / ny 802.11, b / g / ny cuál es mejor?
- ¿Cómo ayuda la transformación rápida de Fourier en la multiplicación polinómica más rápida?
- Cómo resolverlo y (x) ” = h / (y (x)) ^ 2 donde h es constante
Uno de esos casos especiales triviales es el tamaño de entrada . Si puede probar que el algoritmo tiene que examinar una gran cantidad de datos, sabrá que su tiempo de ejecución debe ser al menos proporcional a la cantidad de dichos datos. El ejemplo canónico aquí: el algoritmo óptimo que determina si una matriz A de elementos n sin clasificar dada contiene un elemento dado x se ejecuta en [math] \ Theta (n) [/ math] en el peor de los casos porque tiene que examinar todos los elementos de R. (Si se te ocurre un algoritmo más rápido, no puede ser completamente correcto: si nunca examinas todos los elementos de A, ciertamente puedo obligarte a dar una respuesta incorrecta en algunas entradas). Por lo tanto, la búsqueda lineal es un algoritmo óptimo por este problema
Complementando eso, el otro caso trivial es el tamaño de salida . Un algoritmo que calcula y genera los primeros n números primos no puede ejecutarse más rápido que en [math] \ Theta (n) [/ math] simplemente porque tiene que generar n números. Un algoritmo que calcula y genera todos los primos que no exceden n no puede ejecutarse más rápido que en el tiempo [matemático] \ Theta (n / \ log n) [/ matemático] porque, asintóticamente, hay tantos primos para generar.
Una de las pocas técnicas conocidas que pueden producir límites inferiores ligeramente no triviales son los límites inferiores teóricos de la información . Hay una clase de problemas en los que la entrada es pequeña, la salida es pequeña y, sin embargo, necesitamos más tiempo para resolverlos porque el algoritmo necesita obtener suficiente información para producir la salida correcta. Los dos ejemplos canónicos aquí son buscar un elemento en una matriz ordenada y clasificar una matriz usando solo comparaciones de elementos. Por ejemplo, considere ordenar una matriz de n elementos de elementos distintos. Hay n! posibles permutaciones de la matriz, y el algoritmo de clasificación debe determinar cuál de estos n! permutaciones candidatas es la correcta que produce la matriz ordenada. Cada comparación elimina a lo sumo la mitad de los candidatos (es decir, le da a lo sumo un poco de información). Por lo tanto, el menor número de comparaciones necesarias para eliminar a todos los candidatos, excepto uno, es [math] \ log_2 (n!) [/ Math], que es asintóticamente [math] \ Theta (n \ log n) [/ math]. Por lo tanto, los algoritmos clásicos como MergeSort y HeapSort son algoritmos de clasificación óptimos basados en la comparación. Del mismo modo, la búsqueda binaria es lo mejor que puede hacer al buscar un elemento en una matriz ordenada.
¿Qué hay más allá de estos ejemplos bastante triviales? Bueno, hay algunos casos más en los que sabemos cómo demostrar que algún problema en particular es difícil, pero la mayoría de nuestro mapa actualmente dice que hic sunt leones . Nadie lo sabe. Como dije anteriormente, la pregunta de si P es igual a NP es solo una pequeña faceta de este gran problema.
Por ejemplo, considere un problema estándar de NP completo: determinar si un gráfico de n -vértices contiene un ciclo hamiltoniano. No sabemos si este problema puede resolverse en tiempo polinómico. Probablemente no. Ciertamente es bastante difícil. Nadie pudo resolverlo en [matemáticas] \ Theta (n ^ {1000}) [/ matemáticas] y la mayoría de los investigadores esperan que no exista dicho algoritmo. Pero si el problema es tan difícil, seguramente podemos llegar a un límite inferior en su complejidad, ¿verdad?
Bien. Existe el límite inferior del tamaño de entrada trivial: el algoritmo debe ejecutarse en [math] \ Omega (n ^ 2) [/ math], porque un gráfico con n vértices puede tener [math] \ Theta (n ^ 2) [/ matemáticas], por lo que necesitamos tiempo cuadrático solo para leer la entrada.
Y eso es. Por el momento, no sabemos nada más. Olvídate de P = NP. No tenemos idea de cómo demostrar que el problema del ciclo hamiltoniano no se puede resolver en [matemáticas] \ Theta (n ^ 2) [/ matemáticas].