Sulle prove nella complessità descrittiva

Question

Nella complessità descrittiva, abbiamo teoremi che assomigliano a $ mathrm {eso} = mathrm {np} $ o "su strutture linearmente ordinate, $ fo (lfp) = p $", ma non capisco davvero le prove di quelli.

Per quest'ultimo, l'uguaglianza intuitiva significa davvero che l'affermazione "$ mathcal a model varphi $" può essere verificata per essere vera su una struttura linearmente ordinata $ mathcal a $ in tempo $ n^k $ iff $ varphi $ è espressibile in alcune logiche di fixpoint. L'inclusione da destra a sinistra legge quindi $ forall m ; mathrm {politime ; tm}, esiste varphi in mathrm {fo (lfp)} quad a sinistra [ mathcal a modelli varphi leftrightarrow m ( mathcal a) = 1 destra] $.

La prova che mi è stata insegnata in classe per l'inclusione dal diritto a sinistra va come segue: da una macchina Turing M (con un set di stati $ s $), costruiamo una formula sulla lingua $ {t_0, t_1 } Cup {H_i: i in s } $, dove tutte le relazioni sono di Arity $ 2k $. Questa formula afferma che la struttura su cui viene valutata è un calcolo corretto di $ m $ che termina in uno stato accettante. Come dimostra il teorema? Naturalmente, esiste una biiezione tra l'accettazione di calcoli di $ m $ e strutture $ mathcal a $ st $ m ( mathcal a) = 1 $, ma la dichiarazione del teorema non menziona questa biiezione. Secondo me, la formula $ varphi $ che creiamo dovrebbe davvero controllare le proprietà di $ mathcal a $ e non proprietà del calcolo di $ m $ su $ mathcal a $ ... dov'è il mio errore? Sto pensando troppo a questo?