Recognition and dualization of disguised bidual Horn functions

✍ Scribed by Thomas Eiter; Toshihide Ibaraki; Kazuhisa Makino

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 109 KB
• Volume: 82
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00301-5

✦ Synopsis

We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual f d . While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ϕ [Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ϕ and its dual ϕ d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ϕ (i.e., ϕ becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs.