期刊论文详细信息
Mathématiques et sciences humaines. Mathematics and social sciences | |
Segmentation de la sériation pour la résolution de #SAT | |
Rouat, Valérie1  Lerman, Israël-César1  | |
关键词: 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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201912020428603ZK.pdf | 123KB | download |