¿Es realmente posible probar límites inferiores?

24

Dado cualquier problema computacional, ¿es realmente posible la tarea de encontrar límites más bajos para tal cálculo? Supongo que se reduce a cómo se define un solo paso computacional y qué modelo usamos para la prueba, pero dado eso, ¿realmente demostramos un límite inferior en general? Lo que quiero decir es que ¿podemos probar algo como "el problema no puede resolverse más rápido que el tiempo t ( X ) " en lugar de "el problema X puede resolverse en el tiempo t ( X ) o más rápido"?Xt(X)Xt(X)

He tratado de encontrar información específicamente sobre límites inferiores y pruebas de ellos, pero realmente no puedo encontrar nada de interés, ¿alguna recomendación sobre libros / documentos / sitios web sobre el tema?

hsalin
fuente

Respuestas:

19

Podemos probar absolutamente tales cosas.

Muchos problemas tienen límites inferiores triviales, como el hecho de que encontrar el mínimo de un conjunto de números (que no están ordenados / estructurados de ninguna manera) lleva al menos Ω ( n ) tiempo. La prueba de esto es simple: un algoritmo hipotético que se ejecuta en o ( n ) tiempo no puede examinar todos los números en la entrada. Entonces, si ejecutamos el algoritmo en alguna entrada, podríamos observar que nunca examinó un elemento particular de la entrada. Cambiando ese elemento al mínimo, podemos hacer que el algoritmo falle.norteΩ(norte)o(norte)

Un límite inferior menos trivial es el límite inferior para la clasificación en el modelo basado en la comparación. La prueba de esto va a lo largo de las siguientes líneas: dada una entrada de n números, ¡hay n ! posibles salidas (la entrada podría ser cualquier permutación de la lista ordenada, por lo que la salida también puede ser cualquier permutación de la entrada). Si estamos limitados a hacer solo comparaciones, entonces nuestro algoritmo (en promedio) necesita realizar al menos log 2 ( n ! ) = Ω ( n log n ) comparaciones para poder dar nΩ(norteIniciar sesiónnorte)nortenorte!Iniciar sesión2(norte!)=Ω(norteIniciar sesiónnorte)Diferentes salidas.norte!

Los límites inferiores pueden ser aún más fuertes. Hay varios problemas (especialmente elproblemas duros E X P T I M E ) para los cuales hay un límite inferior exponencial. Los problemas en esta clase incluyen el cálculo de estrategias óptimas para juegos como el ajedrez (generalizado), damas y go. La prueba de esto es a través delTeorema de la jerarquía de tiempo, que establece (sujeto a algunas restricciones en f ):miXPAGSTyoMETROmiF

Dada una función , existe un problema computacional que puede resolverse en el tiempo O ( fF pero no puede resolverse en el tiempo o ( f ( n )O(F(norte)).o(F(norte)Iniciar sesiónnorte)

Básicamente, si puedes pensar en una función , existe un problema que requiere tanto tiempo para resolverse.F

Finalmente, otra vía de no necesariamente probar un límite inferior de tiempo pero algo aún más fuerte es mostrar la indecidibilidad de un problema (por ejemplo, detenerse, correspondencia posterior).

Tom van der Zanden
fuente
El tamaño de entrada o salida son los límites inferiores más comunes.
Raphael
14

Si es posible. El ejemplo clásico es el hecho de que cualquier algoritmo de clasificación basado en comparación requiere para ordenar una lista de longitud n .Ω(norteIniciar sesiónnorte)norte

Sin embargo, los límites inferiores parecen ser mucho más difíciles de probar que los límites superiores. Para demostrar que hay un algoritmo de ordenación que requiere comparaciones , solo necesita exhibir dicho algoritmo (fusionar sort - voila !). Pero para un límite inferior, de alguna manera necesita demostrar que ningún algoritmo en una clase en particular puede resolver su problema. La dificultad de hacerlo se ilustra por el hecho de que solo sabemos que LN LPN PP S P A C EO(norteIniciar sesiónnorte) aunque sabemos que al menos una de esas inclusiones es estricta ( LP S

LnorteLPAGSnortePAGSPAGSSPAGSUNAdomi,
por el teorema de la jerarquía espacial) y la mayoría de la gente piensa que sontodosestricto.LPAGSSPAGSUNAdomi

Por otro lado, Ryan Williams tiene un buen artículo (y una charla, que he escuchado un par de veces) llamado Algorithms for Circuits y Circuits for Algorithms , en el que argumenta que encontrar límites más bajos y encontrar algoritmos no son fundamentalmente todos que diferente Por ejemplo, cita la prueba de la indecidibilidad del problema de detención como un ejemplo de un algoritmo (la máquina universal de Turing) que se usa exactamente para probar un límite inferior (indecidibilidad).

David Richerby
fuente
Creo que esto es lo que busco "... de alguna manera necesitas demostrar que ningún algoritmo en una clase en particular puede resolver tu problema", esta es la parte que encuentro un poco confusa ya que no puedo ver intuitivamente cómo podría hacerlo tal cosa, en general al menos. Como @Tom van der Zanden describió el número mínimo de hallazgos que entiendo, pero ¿ese enfoque es general? Me refiero a general en cuanto a tener ese tipo de argumento al construir las pruebas. Gracias por el enlace también.
hsalin
1
@ user1288420 No estás solo. Si alguien pudiera ver intuitivamente cómo demostrar que ningún algoritmo en una clase en particular puede resolver algún problema, ¡tendríamos muchos más resultados de límite inferior! Por lo general, debe encontrar alguna propiedad que tenga cada algoritmo de la clase y demostrar que esa propiedad evita que se resuelva algún problema. Por ejemplo, cada máquina de Turing que se ejecuta en tiempo sublineal tiene la propiedad de que ni siquiera puede leer toda su entrada. Eso significa que no puede resolver la mayoría de los problemas. Eso es trivial; desafortunadamente, los casos más interesantes parecen ser imposiblemente difíciles.
David Richerby
3

Para tomar un ejemplo trivial, no puede encontrar el número más grande de un conjunto de norte

Sin embargo, hay un punto en la pregunta que requiere más comentarios sobre el límite inferior (o los límites de complejidad en general).

En realidad, la elección de lo que es un solo paso computacional es irrelevante, siempre y cuando los pasos computacionales puedan considerarse que tienen un límite superior constante (y un límite inferior). El resultado de la complejidad será el mismo ya que se define hasta una constante. Tomar 3 comparaciones como operaciones unitarias, o solo una, no hace ninguna diferencia.

Lo mismo es cierto con respecto al tamaño de los datos que sirve de referencia para evaluar el costo del cálculo. Tomar un solo entero o dos enteros como unidad de tamaño no hace ninguna diferencia.

Sin embargo, las dos opciones deben estar relacionadas.

norteIniciar sesiónnorteO(Iniciar sesiónnorte) dígitos para representar un número. Entonces, por supuesto, la suma y la comparación ya no son operaciones unitarias, y su costo depende de los valores de los operandos.

Si una operación puede considerarse que tiene un costo unitario está estrechamente relacionada con qué datos pueden considerarse que tienen un tamaño unitario. Y eso depende del nivel de abstracción que elija para su modelo de cálculo.

babou
fuente
Encontrar todas las ocurrencias de un patrón en una cadena de manera trivial requiere leer toda la cadena: si el patrón es "a", no puede encontrar todas las ocurrencias sin verificar si cada carácter de la cadena.
David Richerby
1
@DavidRicherby En realidad no siempre. El algoritmo de Boyer-Moore comienza desde el final del patrón, saltando así en la cadena. Si el intento de coincidencia falla, no tiene que leer el comienzo de la cadena. Y también tiene una optimización similar al algoritmo de Knuth-Morris-Pratt para omitir los intentos que fallan debido a la estructura del patrón. Por supuesto, hay patrones que requieren leer la cadena completa.
babou
@DavidRicherby ¿Por qué preguntaste eso?
babou
No entiendo tu segundo comentario. Su respuesta original contenía un reclamo incorrecto. Por supuesto, sabía que era incorrecto: ¡así fue como pude señalarlo! Es posible que otras personas no supieran que era incorrecta, por lo que les habría resultado confuso dejar la respuesta tal como estaba.
David Richerby
1
@DavidRicherby Mi punto es que entendiste lo que quise decir. Debería haber dicho puede no más que no . Esto no requería un estilo de comentario que hiciera creer a los lectores que estaba hablando tonterías. Y al hacerlo, cometió exactamente el mismo error descuidado: al afirmar que " Encontrar todas las ocurrencias de un patrón en una cadena trivialmente requiere leer la cadena completa ", cuando debería haber dicho " Encontrar todas las ocurrencias de un patrón en una cadena puede requerir leyendo toda la cadena ". Solo pretendía afirmar que leer la entrada puede no ser siempre necesario, para mitigar mi ejemplo anterior.
babou