Un billón es solo una constante, entonces O ([matemática] 10 ^ 9 [/ matemática]) = O ([matemática] 1 [/ matemática]). Su pregunta parece realmente malformada y se basa en un malentendido. Las medidas de complejidad no miden cuánto tiempo lleva hacer una sola tarea. Miden cómo aumenta el tiempo requerido para hacer un tipo de tarea a medida que aumenta el tamaño de la tarea. Por ejemplo, ordenar una lista arbitraria de n elementos es O ( n log ( n )), por lo que si duplica el tamaño de la lista, debe esperar que tome un poco más del doble de tiempo para ordenarla.
No tengo idea de lo que quiere decir con “jueces en línea” que “aceptan” la complejidad.
Una de las funciones más complejas posibles es el problema Busy Beaver. BB ( n ) es el número máximo de 1s que cualquier máquina de Turing con n estados puede imprimir en su cinta antes de detenerse. Por supuesto, tenemos que insistir en que la máquina finalmente se detenga; de lo contrario, es fácil diseñar una máquina trivial que obtenga infinitos 1s simplemente haciendo “imprimir 1 y moverse hacia la derecha” en cada ciclo.
- ¿Qué son los algoritmos? ¿Cómo trabajan?
- ¿Hay algún algoritmo de clasificación que sea sustancialmente más rápido que QuickSort?
- Teoría de grafos: ¿en qué se diferencian los árboles de expansión construidos a partir de Prim de los árboles de expansión construidos a partir de Kruskal?
- ¿Has visto algún trabajo hacia el cierre transitivo de la alineación de secuencias y las matrices de sustitución?
- ¿Cómo funcionan los algoritmos y la estructura de datos cuando procesamos cualquier solicitud en un sitio web?
Al principio parece que esto debería ser difícil pero no imposible. Todo lo que necesita hacer es enumerar todas las máquinas de Turing posibles con n estados, simularlas hasta que se detengan (o no) y elegir la más alta. Pero hay varios problemas. Primero, es fácil demostrar que una máquina se detiene (simplemente ejecútela hasta que se detenga), pero en general puede ser imposible demostrar que una máquina NO se detiene (no puede esperar hasta el infinito). Por lo tanto, es fácil probar los límites inferiores a BB ( n ), pero es difícil probar los límites superiores.
No obstante, para muy pequeños n hemos podido analizar todas las TM y calcular BB. BB (1) [matemáticas] = 1 [/ matemáticas], BB (2) [matemáticas] = 4 [/ matemáticas], BB (3) [matemáticas] = 6 [/ matemáticas] y BB (4) [matemáticas] = 13 [/ matemáticas]. Hasta aquí todo bien. Pero esas son todas las respuestas exactas que conocemos. Para n superior solo tenemos límites inferiores. BB (5) [matemáticas] \ ge 4098 [/ matemáticas], BB (6) [matemáticas]> 3.5 × 10 ^ {18267} [/ matemáticas], BB (7) [matemáticas]> 10 ^ {2 \ veces 10 ^ {10 ^ {10 ^ {18705352}}}} [/ matemáticas].
Pero espera, se pone peor. Para n> 7918, podemos demostrar que es imposible calcular BB ( n ) dentro de la teoría de conjuntos de Zermelo-Frankel, que es la base de la mayoría de las matemáticas modernas. Lo frustrante aquí es que sabemos que hay una respuesta: BB ( n ) debe existir porque solo hay un número finito de máquinas de estado n , cada máquina se detiene o no, y entre las máquinas que detienen una de ellas debe escribir más 1s. Pero podemos demostrar que nunca podremos averiguar cuál es, o cuántos 1s escribe. BB ( n ) crece más rápido que cualquier función computable.
Entonces, ¿pueden los “jueces en línea” “aceptar” O (BB ( n ))? Dígame usted.
