Intuitivamente, los teoremas dicen que puedes hacer más cosas (es decir, decidir más idiomas) si tienes más tiempo o espacio. Por ejemplo, si la longitud de entrada es n, hay idiomas que se pueden decidir en el tiempo n ^ 3, pero no en el tiempo n². Lo mismo vale para el espacio.
La prueba de manera informal es la siguiente: Tome cualquier enumeración de todas las máquinas de Turing. Construimos una máquina M de Turing que, para la entrada n, simula la máquina con el número n en la entrada n. Sin embargo, no esperamos cantidades arbitrarias de tiempo hasta que la simulación haya terminado, sino que solo simulamos la enésima máquina para los pasos T (n). Si acepta, M rechaza. Si rechaza o no termina, M acepta. Se puede mostrar que M se ejecuta en T (n) ² pasos. Sin embargo, cualquier máquina de Turing M ‘que se ejecuta en pasos T (n), no puede decidir el mismo lenguaje que M que se ejecuta en pasos T (n) significa que la simulación termina y M responde lo contrario de M’ para al menos una entrada . (De hecho, para un número infinito de entradas, pero esto es irrelevante aquí).
Es bastante fácil demostrar que una máquina con tiempo de ejecución T (n) puede simularse en pasos T (n) ². Es más complicado mostrar que, de hecho, no necesita pasos T (n) ² pero puede obtener un factor mejor. Sin embargo, el caso de T (n) ² es suficiente para mostrar que existe una jerarquía de tiempo.
Para la complejidad del espacio, se puede llevar a cabo la misma prueba, pero se puede demostrar que la sobrecarga de espacio requerida para simular las máquinas de turing es solo un factor constante. Por lo tanto, obtienes una jerarquía aún más estricta para la complejidad del espacio.
Como puede ver en este boceto de prueba, la sugerencia es que cuando tenga suficientes recursos, puede usarlos para simular el comportamiento de una máquina con menos recursos y, por lo tanto, crear problemas que esa máquina no puede resolver.
- ¿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?
- Si alguien encuentra un algoritmo para resolver un problema np en p, ¿significa que p = np?
- ¿Qué campo en informática es un equilibrio entre matemática y programación?
- ¿Cuál es el propósito del software matemático computacional?
- Soy un desarrollador, pero me falta mi habilidad matemática. Con un BSc en CS y un MSc en IS, ¿qué debo saber y cómo puedo identificar dónde necesito ayuda?
