Sur la satisfaction pour 2 variables.
-
06-11-2019 - |
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:
- Satisfaction de $ mathbf {fo ^ 2} $ est dans $ mathbf {ntime} (2 ^ {o (n)}) $.
- 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:
- Est-il facile de voir que ces deux lemmes impliquent $ mathbf {nexptime} $-COMPLETINnité?
- 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
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange