Estoy tratando de entender el documento sobre p-Optimal Proof Systems and Logic para PTIME . Hay una noción llamada sistemas de prueba en el documento y no entiendo:
... Identificamos problemas con subconjuntos de en .
Creo que la intuición es que codificamos una determinada estructura en (por ejemplo, gráficos no dirigidos) y los subconjuntos de estas estructuras son problemas (por ejemplo, gráficos planos).
Un sistema de prueba para un problema es una función sobreyectiva computable en tiempo polinómico. P : Σ ∗ → Q
Ahora, una posibilidad es decir es el conjunto de todos los modelos posibles en una determinada estructura (por ejemplo, todos los gráficos no dirigidos). Pero eso no tiene sentido porque ¿por qué deberían asignarse gráficos no dirigidos en un subconjunto? Podría codificarse en máquinas de turing, pero esto tampoco tiene sentido ...
¿Algunas ideas?