Sulla soddisfazione per la gente a 2 variabili che è nexptime-complet

Question

Permettere $ mathbf {fo^2} $ Sii il frammento della logica del primo ordine costituito da frasi con al massimo due variabili e senza simboli di funzione. È risaputo che la soddisfazione per $ mathbf {fo}^2 $ è decidabile (vedi [1], per esempio). Inoltre, nello stesso documento, si sostiene $ mathbf {fo^2} $ La soddisfazione è $ mathbf {nexptime} $-Come, e che questo risultato segue da questi due lemmi:

1. Soddisfazione per $ mathbf {fo^2} $ è in $ mathbf {ntime} (2^{o (n)}) $.
2. Soddisfazione per $ mathbf {fo^2} $ ha un limite di complessità inferiore della forma $ mathbf {ntime} (2^{cn/ log {n}}) $ Per qualche costante positiva $ c $.

Non ho molto background nella teoria della complessità, quindi questo mi ha lasciato due domande:

1. È facile vedere che questi due lemmi implicano $ mathbf {nexptime} $-completezza?
2. Questo risultato non è contraddittorio? Per definizione, $ mathbf {nexptime} = bigcup_ {k in mathbb {n}} mathbf {ntime} (2^{n^k}) $, e dal teorema della gerarchia non deterministica che abbiamo per qualsiasi $ i, j in mathbb {n} $ Quello $ mathbf {ntime} (2^{n^i}) SubsetNeq mathbf {ntime} (2^{n^j}) $ Se $ i <j $. Quindi mi chiedo come un problema completo per la classe possa risiedere al "gradino più basso" della scala-è questo perché le riduzione Karp possono far esplodere le dimensioni di un input polinomia?

---

RIFERIMENTI

[1] Sul problema decisionale per la logica del primo ordine a due variabili-Grädel, Kolaitis e Vardi