Dans cette thèse, nous nous intéressons d’un point de vue théorique, algorithmique et expérimental à deux problèmes fondamentaux : la déduction d’une entité A dans une entité B, c’est-à-dire A se déduit-elle de B, ou encore les informations contenues dans B se trouvent-elles dans A, et l’interrogation de bases de connaissances, c'est-à-dire la recherche de réponses à une question dans une base de connaissances. Ces problèmes se retrouvent sous différentes formes selon la nature des entités et de la base de connaissance. Ainsi, si nous considérons des requêtes conjonctives et une base de données quelconque, nous obtenons les problèmes fondamentaux en Bases de Données (BD) suivants : l’inclusion de requêtes conjonctives et le Query Answering (recherche des réponses à une requête dans une BD). Si nous considérons des formules du fragment existentiel conjonctif de la logique du 1er ordre, noté FOL^ , la base de connaissances étant alors constituée d’un ensemble de formules), nous retrouvons les problèmes de déduction et d’interrogation. De même si nous nous plaçons dans le fragment universel disjonctif, noté FOL^{\cup}, nous obtenons notamment le problème d’inclusion de clauses, fondamental pour les techniques d’ILP (Inductive Logic Programming). Tous ces problèmes sont connus pour être NP-complets.
Nous nous intéressons plus précisément à l’impact induit par l’augmentation de l’expressivité du langage choisi (FOL^, BD…), en ajoutant la négation atomique et en considérant le monde ouvert (si une information n’apparaît pas, elle n’est pas automatiquement fausse). Il a été prouvé que les problèmes changent alors de classe de complexité pour passer de NP-complets à \Pi_2^p-complets. Néanmoins, très peu de travaux s’intéressent à ces problèmes (trois travaux à notre connaissance). L’objectif est, dans un premier temps de formaliser l’impact de la prise en compte de la négation atomique sur les deux problèmes susmentionnés (qu’est-ce que devient la définition d’une réponse par exemple), puis de mettre en place des algorithmes « efficaces » pour les résoudre et enfin de mettre en place une méthodologie expérimentale et de présenter une analyse expérimentale approfondie (recherche des valeurs des paramètres rendant la résolution du problème difficile, comparer expérimentalement les différentes approches et différentes heuristiques etc.)