Question

Selon la page Wikipedia sur Théorie de la complexité descriptive:

En présence d'ordre linéaire, la logique de premier ordre avec un opérateur de points fixes le moins fixe donne P, les problèmes résolubles en temps polynomial déterministe.

La logique existentielle du second ordre donne NP, comme mentionné ci-dessus.

Si P = NP ne serait-il pas possible de convertir une logique existentielle de second ordre en une logique de premier ordre correspondante avec un opérateur de points le moins fixe? Cela impliquerait également une bijection entre ces ensembles (y a-t-il une bijection entre la logique existentielle du second ordre et la logique de premier ordre avec un opérateur de points le moins fixe?).

Ma compréhension est que la logique du premier ordre ne peut pas exprimer la logique de second ordre - pourquoi cela ne prouve-t-il pas P! = Np?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top