Cartesian and statistical approches of the satisfiability problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1992

Cartesian and statistical approches of the satisfiability problem

Résumé

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".

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1685.pdf (2.36 Mo) Télécharger le fichier

Dates et versions

inria-00076908 , version 1 (29-05-2006)

Identifiants

  • HAL Id : inria-00076908 , version 1

Citer

Israël-César Lerman. Cartesian and statistical approches of the satisfiability problem. [Research Report] RR-1685, INRIA. 1992. ⟨inria-00076908⟩
49 Consultations
56 Téléchargements

Partager

Gmail Facebook X LinkedIn More