Muestre una función que sea construible en el espacio pero no construible en el tiempo.f(n)f(n)f(n) ¿Está este problema relacionado con una posible separación entre las clases de complejidad DTIME (f (n)) y SPACE (f
En esta pregunta , se mencionó que existen versiones descriptivas de complejidad del teorema de Rice. Encontré una prueba del siguiente teorema: Dada una clase de complejidad C , las propiedades no triviales de los lenguajes en C no se pueden calcular en C Anteriormente había publicado la...
El teorema de la jerarquía de tiempo permite mostrar que, por ejemplo, hay problemas en P que una máquina de Turing no puede resolver en un tiempo menor que const * n ^ 2. Pero dale algunos consejos a la máquina Turing y todas las apuestas están canceladas. Todavía no se puede demostrar que incluso...
¿Alguno de ustedes conoce una referencia para el siguiente resultado (sorprendentemente tedioso de probar)? Dado un gráfico plano conectado con vértices y aristas, tiene un separador de vértices de tamaño .GGGnnnn+tn+tn+tO(t√+1)O(t+1)O(