Sobre pruebas en complejidad descriptiva

Question

En la complejidad descriptiva, tenemos teoremas que parecen $ mathrm {eSO} = mathrm {np} $ o "en estructuras ordenadas linealmente, $ fo (lfp) = p $", pero realmente no entiendo las pruebas de aquellos.

Para este último, la igualdad intuitiva realmente significa que la declaración "$ Mathcal a modelos varphi $" puede verificarse para que sea verdadera en una estructura ordenada linealmente $ mathcal a $ en el tiempo $ n^k $ iff $ varphi $ es expresable en alguna lógica de fijación. La inclusión de derecha a la izquierda luego lee $ forall m ; Mathrm {Polytime ; tm}, existe varphi in mathrm {fo (lfp)} quad left [ mathcal a models varphi leftrightarrow m ( mathcal a) = 1 right] $.

La prueba de que me han enseñado en clase para la inclusión de derecha a izquierda es la siguiente: de una máquina de Turing M (con un conjunto de estados $ S $), construimos una fórmula en el lenguaje $ {t_0, t_1 } cup {h_i: i in s } $, donde todas las relaciones son de aridad $ 2k $. Esta fórmula dice que la estructura en la que se está evaluando es un cálculo correcto de $ M $ que termina en un estado de aceptación. ¿Cómo prueba esto el teorema? Por supuesto, existe una biyección entre aceptar cálculos de $ m $ y estructuras $ mathcal a $ st $ m ( mathcal a) = 1 $, pero la declaración del teorema no menciona esta biyección. En mi opinión, la fórmula $ varphi $ que creamos realmente debería verificar las propiedades de $ mathcal a $, y no las propiedades del cálculo de $ m $ en $ mathcal a $ ... ¿dónde está mi error? ¿Estoy pensando demasiado?