A Short Implicant of a CNF Formula with Many Satisfying Assignments

作者：Kane Daniel; Watanabe Osamu^*

来源：Algorithmica, 2016, 76(4): 1203-1223.

DOI：10.1007/s00453-016-0125-z

• Short satisfying partial assignment
• Conjunctive normal form formula
• Large satisfying assignment ratio

Consider any Boolean function that has more than satisfying assignments for some , , and that can be expressed by a CNF formula with at most clauses for some . Then how many variables do we need to fix in order to satisfy F? We show that one can always find some "short" partial assignment on which F evaluates to 1 by fixing at most variables for some constant ; that is, F has an implicant of size . A lower bound for such is also shown in terms of and d. We also discuss an algorithm for obtaining a short partial assignment. For any and such that , we show a deterministic algorithm that finds a short partial assignment in -time (By we mean .) for some and for any CNF formula with at most clauses having more than satisfying assignments.

• 出版日期2016-12