Sur la satisfaction pour 2 variables.

Question

Laisser $ mathbf {fo ^ 2} $ être le fragment de la logique de premier ordre composé de phrases avec au plus deux variables et aucun symbole de fonction. Il est bien connu que la satisfaction $ mathbf {fo} ^ 2 $ est décideable (voir [1], par exemple). De plus, dans ce même article, il est soutenu que $ mathbf {fo ^ 2} $ La satisfaction est $ mathbf {nexptime} $-Callete, et que ce résultat découle de ces deux lemmes:

1. Satisfaction de $ mathbf {fo ^ 2} $ est dans $ mathbf {ntime} (2 ^ {o (n)}) $.
2. Satisfaction de $ mathbf {fo ^ 2} $ a une complexité plus faible de la forme $ mathbf {ntime} (2 ^ {cn / log {n}}) $ Pour une constante positive $ c $.

Je n'ai pas beaucoup de contexte dans la théorie de la complexité, donc cela m'a laissé deux questions:

1. Est-il facile de voir que ces deux lemmes impliquent $ mathbf {nexptime} $-COMPLETINnité?
2. Ce résultat n'est-il pas contradictoire? Par définition, dollars, et par le théorème de hiérarchie temporelle non déterministe que nous avons pour tout $ i, j in mathbb {n} $ ce $ mathbf {ntime} (2 ^ {n ^ i}) subsetneq mathbf {ntime} (2 ^ {n ^ j}) $ si $ i <j $. Je me demande donc comment un problème terminé pour la classe peut se situer au "l'échelle le plus bas" de l'échelle - est-ce parce que les réductions de Karp peuvent exploser la taille d'un polynôme d'entrée?

---

RÉFÉRENCES

[1] Sur le problème de décision pour la logique de premier ordre à deux variables - Grädel, Kolaitis et Vardi