Abstract FR:

1. Nous caracterisons la classe des spectres des formules du premier ordre sur le vocabulaire restreint a un seul symbole de fonction unaire. Par consequent, cette classe est close par complement (reponse partielle aux problemes d'asser et de fagin), et les classes de requetes definissables en logique existentielle du second ordre avec respectivement un et deux quantificateurs sur des fonctions unaires sont separees. 2. Nous analysons le pouvoir d'expression de la logique existentielle monadique du second ordre (np monadique) avec differentes relations predefinies, en particulier une grille carree. Nous pouvons ramener des questions de definissabilite en logique existentielle du second ordre d'arites superieures a des questions equivalentes en np monadique avec une grille carree predefinie. A) nous discutons la question de la definissabilite de la connexite de graphes en np monadique avec une grille carree predefinie. Des consequences inattendues d'une reponse positive sont demontrees. D'autre part, certains resultats ayant jusqu'alors uniquement des preuves considerees comme difficiles sont des consequences d'une reponse negative, en particulier les separations dans la hierarchie de m. Ajtai. B) nous etudions la question d'une separation des classes de requetes definissables en logique existentielle du second ordre avec quantification sur des fonctions unaires et de np monadique sur des grilles carrees colorees. Nous montrons que cette separation implique l'existence d'une np-propriete de graphes qui n'est pas definissable en quantifiant sur une seule relation binaire (une vieille question ouverte posee par r. Fagin). En particulier, l'existence d'une propriete d'ensembles carres colores qui est definissable avec quantification sur des fonctions unaires, mais pas avec seulement deux fonctions, implique une reponse a la question de r. Fagin.