HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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".
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Monday, May 29, 2006 - 11:18:57 AM
Last modification on : Tuesday, June 15, 2021 - 4:26:31 PM
Long-term archiving on: : Friday, May 13, 2011 - 8:52:37 PM


  • 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⟩



Record views


Files downloads