Cartesian and statistical approches of the satisfiability problem

Israël-César Lerman 1
1 CADO - Classification et Analyse des DOnnées
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, UR1 - Université de Rennes 1, INSA Rennes - Institut National des Sciences Appliquées - Rennes
Abstract : This work is devoted to a new and systematic treatment of the different questions arised in the original study (Simon & Dubois 1989). We consider both formal and statistical aspects with a set theoretic and geometrical representation. On the other hand we adopt the combinatoric and statistical point of view which is usual in our approach of data classification. Our synthetic formulation makes clearer and improves the algorithms or calculations, previously considered (cf. above reference). On the other hand and mainly, we propose new algorithms and new calculations which enable to"see"the limit of the complexity reduction that we can expect. For this respect, we essentially distinguish the problem of the evaluation of the number of solution and that one of the recognition of the satisfiability instances. Two cases are studied concerning real observed and random systems of clauses. In our formalization we represent a clause by a logical and geometrical object that we call a "pinpoint cylinder". On the other hand, the "inclusion and exclusion" formula plays an important role in our evaluations. The new algorithms that we present take into account the marginal statistical distributions of the variables. On the other hand, we introduce in these algorithms parallel procedures and-in a relevant way our approach in data classification. The latter can play an important role in complexity reduction of a SAT problem. In each of both aspects: evaluation of the solutions and recognition of the satisfiability, significant results are obtained in the context of the generation of a random system of clauses. The randommess is according to a model that we usually consider in our approach of data classification, for measuring associations (between "pinpoint cylinders", here); and that we call,"hypothesis of no relation".
Type de document :
[Research Report] RR-1685, INRIA. 1992
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:18:57
Dernière modification le : vendredi 16 novembre 2018 - 01:26:10
Document(s) archivé(s) le : vendredi 13 mai 2011 - 20:52:37



  • HAL Id : inria-00076908, version 1


Israël-César Lerman. Cartesian and statistical approches of the satisfiability problem. [Research Report] RR-1685, INRIA. 1992. 〈inria-00076908〉



Consultations de la notice


Téléchargements de fichiers