Gradualidad de los reconocedores de tiempo polinómico

Question

¿Existe algún contraejemplo o teorema para la siguiente pregunta?

Ejemplos:

Veamos primero algunos ejemplos para hacernos una idea. Dejaremos que $n$ sea la longitud de la entrada en caracteres. Todos los ejemplos son reconocedores que no pretenden producir ninguna salida más que "aceptar" o "rechazar".

1. Búsqueda lineal. Se nos da una secuencia de caracteres. Se lee un carácter de entrada; si coincide con lo buscado, terminamos con éxito. Si no, esa entrada puede ser desechada ya que no coincide y pasamos al siguiente carácter de la entrada.

2. Análisis sintáctico determinista libre de contexto. Una palabra de entrada se lee y se desplaza a la pila o se reduce con la pila existente, para formar una nueva pila. Como el analizador sintáctico es sólo un reconocedor, no tenemos que recordar la palabra de entrada original una vez que se ha reducido a un no terminal.

3. Coincidencia final de caracteres. Este es un ejemplo artificial para aclarar la cuestión. El formato es $n-1$ personajes de entrada que no importan y un personaje final que sí. Si el carácter final coincide con un carácter constante fijo, tenemos éxito, de lo contrario fallamos. De nuevo, podemos simplemente desechar todos los caracteres no finales a medida que se leen, ya que no importan.

En cada caso, se está haciendo un progreso gradual hacia una solución cada vez que se lee una entrada, donde "progreso gradual" es una transformación gradual de la configuración de la máquina en un estado final tal que en algún paso durante la transformación, se pierde suficiente información para que sea imposible reconstruir la entrada original: es decir, el cálculo se vuelve irreversible en la medida en que es imposible reconstruir la entrada original. ¿Es cierto el siguiente párrafo para todos los reconocedores de tiempo polinómico? ¿Hay algún teorema que lo respalde? ¿O existe un contraejemplo?

Pregunta:

(Notación: L es una lengua en P y M es un reconocedor de tiempo polinómico para L .) Para todos los L existe un M (sujeto a las restricciones que se indican a continuación) cuando hay progreso (definido anteriormente) durante el cálculo. Más concretamente, no hay L en P tal que para toda restricción (véase más adelante) M para L no hay progreso durante la primera $n-1$ caracteres del cómputo y luego un "flash repentino" que produce la respuesta al encontrar el último carácter de entrada.

Se nos dan dos restricciones:

1. Irreductibilidad. No existe una reducción en tiempo polinómico de una máquina "súbita" a una gradual, por lo que no podemos crear una máquina envolvente que agrupe las entradas y al final simplemente la pase a una máquina gradual para que realice realmente el cálculo.

2. Incompresibilidad. También se nos da que no existe ninguna transformación de compresión en tiempo polinómico de una entrada $n$ caracteres de longitud a un tamaño sustancialmente inferior al lineal: es decir, de una clase de complejidad inferior a $O(n)$ ; véase el ejemplo 3 anterior (así se eliminan ejemplos muy redundantes).

EDIT: En uno de los comentarios sugerí una salvedad; esto ya no es necesario. En el caso de la concordancia de cadenas, mencioné que existe un algoritmo que simplemente desecha los caracteres iniciales siempre que coincidan, proporcionando así irreversibilidad. En el caso de una cadena de prueba constante, había sugerido una solución de estado finito, pero esto no es necesario ya que simplemente hay una reducción de tiempo polinomial a la primera estrategia de coincidencia de cadenas en este párrafo. Por lo tanto, se retira la salvedad que sugerí; la pregunta se mantiene.

Answer 1

Espero haber entendido ahora correctamente la pregunta tal y como se ha aclarado en los comentarios. Tus definiciones de progreso y reconstructibilidad son algo informales, pero creo que entiendo lo que quieres decir; por favor, corrígeme si todavía estoy interpretando algo mal.

Creo que un contraejemplo lo proporciona un reconocedor en tiempo polinómico de secciones iniciales invertidas de algunos secuencia normal cuyas secciones iniciales se pueden calcular en tiempo polinómico, por ejemplo los dígitos decimales del Constante de Champernowne o, presumiblemente, los dígitos hexadecimales de $\pi$ ("presumiblemente" porque no se sabe, aunque se cree ampliamente, que formen una secuencia normal). Al tratar de decidir si una entrada dada es una sección inicial invertida de este tipo, hay que almacenar toda la entrada hasta llegar al final, ya que no hay forma de saber con qué partes de la secuencia hay que comparar la entrada antes de llegar al final, y todos los patrones finitos posibles se dan con una frecuencia infinita en una secuencia normal, por lo que nunca se puede excluir que lo que se ha visto hasta ahora pueda ser el principio de una de las secciones iniciales invertidas; que lo sea siempre depende potencialmente de un solo trozo de la entrada ya vista.