Segmentation de la sériation pour la résolution de ­ #SAT

Mathématiques et sciences humaines. Mathematics and social sciences

Rouat, Valérie¹  Lerman, Israël-César¹ 

关键词: classification;    satisfiability;    complexity theory;    counting;    #p-complete problems;    seriation;   

DOI  :  10.4000/msh.2793

学科分类：数学（综合）

来源: College de France * Ecole des Hautes Etudes en Sciences Sociales (E H E S S)

【 摘 要 】

We propose here a general method for approximating the number of solutions of a boolean formula in conjunctive normal form F. By applying the principle "divise to resolve", this method reduces considerably the computational complexity. It is based on cutting a seriation established on an incidence data table associated with F. Moreover, the independence probability concept is finely exploited. Theoretical justification and intensive experimentation validate the proposed method.

【 授权许可】

Unknown