Recognition and dualization of disguised
✍
Thomas Eiter; Toshihide Ibaraki; Kazuhisa Makino
📂
Article
📅
2002
🏛
Elsevier Science
🌐
English
⚖ 109 KB
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.