Monotone DNF Formula That Has a Minimal or Mazimal Number of Satisfying Assignments
We consider the following extremal problem: Given three natural numbers n, m and l, what is the monotone DNF formula that has a minimal or maximal number of satisfying assignments over all monotone DNF formulas on n variables with m terms each of length 1? We first show that the solution to the minimization problem can be obtained by the KruskalKatona theorem developed in extremal set theory. We also give a simple procedure that outputs an optimal formula for the more general problem that allows the lengths of terms to be mixed. We then show that the solution to the maximization problem can be obtained using the result of Bollobas on the number of complete subgraphs when l=2 and the pair (n, m)satisfies a certain condition. Moreover, we give the complete solution to the problem for the case l=2 and m≤n, which cannot be solved by direct application of Bollobass result. For example, when n=m, an optimal formula is represented by a graph
Takayuki Sato Kazuyuki Amano Eiji Takimoto Akira Maruoka
Dept. of Information Engineering, Sendai National College of Technology Chuo 4-16-1, Ayashi, Aoba, S Department of Computer Science, Gunma University Tenjin 1-5-1, Kiryu,Gunma 376-8515, Japan Graduate School of Information Sciences, Tohoku University Aoba 6-6-05, Aramaki, Sendai 980-8579, Ja Dept. of Information Technology and Electronics, Ishinomaki Senshu University
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
191-203
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）