If one is given a monotone Boolean expression, then replacing all conjunctions by disjunctions produces another monotone Boolean expression for the dual function, following De Morgan's laws.
However, it is crucial in analyzing the complexity of this problem that both the CNF and DNF representations are output.
If only the CNF representation of an unknown monotone function is output, it follows from information theory that the number of function evaluations must sometimes be exponential in the combined input and output sizes.
[3] Therefore, what is desired for these problems is an output-sensitive algorithm, one that takes a small amount of time per output clause.
[4] Bioch & Ibaraki (1995) outline the following algorithm for solving exact learning using a decision subroutine: Each iteration through the outer loop of the algorithm uses a linear number of calls to the decision problem to find the unforced truth assignment, uses a linear number of function evaluations to find a minimal true or maximal false function value, and adds one clause to the output.
[4] A central result in the study of this problem, by Michael Fredman and Leonid Khachiyan, is that monotone dualization (in any of its equivalent forms) can be solved in quasi-polynomial time.
Alternatively, in cases where the answer to the decision problem is no, the algorithms can be modified to return a witness, that is, a truth assignment for which the input formulas fail to determine the function value.
The cleaning step ensures the existence of a variable that belongs to many clauses, causing a significant reduction in the recursive subproblem size.
[1] In more detail, the first and slower of the two algorithms of Fredman and Khachiyan performs the following steps:[1][6] When this algorithm branches on a variable occurring in many clauses, these clauses are eliminated from one of the two recursive calls.
Using this fact, the running time of the algorithm can be bounded by an exponential function of
[1][6] A second algorithm of Fredman and Khachiyan has a similar overall structure, but in the case where the branch variable occurs in many clauses of one set and few of the other, it chooses the first of the two recursive calls to be the one where setting the branch variable significantly reduces the number of clauses.
[1][6] Many special cases of the monotone dualization problem have been shown to be solvable in polynomial time through the analysis of their parameterized complexity.
[2] These include: One application of monotone dualization involves group testing for fault detection and isolation in the model-based diagnosis of complex systems.
[2][12] In biochemical engineering, the enumeration of hitting sets has been used to identify subsets of metabolic reactions whose removal from a system adjusts the balance of the system in a desired direction.
[2] In recreational mathematics, in the design of sudoku puzzles, the problem of designing a system of clues that has a given grid of numbers as its unique solution can be formulated as a minimal hitting set problem.
Thus, the enumeration of minimal hitting sets can be used to find all systems of clues that have a given solution.
This approach has been as part of a computational proof that it is not possible to design a valid sudoku puzzle with only 16 clues.