In theoretical computer science, monotone dualization is a computational problem of constructing the dual of a monotone Boolean function. Equivalent problems can also be formulated as constructing the transversal hypergraph of a given hypergraph, of listing all minimal hitting sets of a family of sets, or of listing all minimal set covers of a family of sets. These problems can be solved in quasi-polynomial time in the combined size of its input and output, but whether they can be solved in polynomial time is an open problem.
Definitions A Boolean function takes as input an assignment of truth values to its arguments, and produces as output another truth value. It is monotone when changing an argument from false to true cannot change the output from true to false. Every monotone Boolean function can be expressed as a Boolean expression using only logical disjunction ("or") and logical conjunction ("and"), without using logical negation ("not"). Such an expression is called a monotone Boolean expression. Every monotone Boolean expression describes a monotone Boolean function. There may be many different expressions for the same function. Among them are two special expressions, the conjunctive normal form and disjunctive normal form. For monotone functions these two special forms can also be restricted to be monotone:
The conjunctive normal form of a monotone function expresses the function as a conjunction ("and") of clauses, each of which is a disjunction ("or") of some of the variables. A clause may appear in the conjunctive normal form if it is true whenever the overall function is true; in this case it is called an implicate, because the truth of the function implies the truth of the clause. This expression may be made canonical by restricting it to use only prime implicates, the implicates that use a minimal set of variables. The conjunctive normal form using only prime implicates is called the prime CNF. The disjunctive normal form of a monotone function expresses the function as a disjunction ("or") of clauses, each of which is a conjunction ("and") of variables. A conjunction may appear in the disjunctive normal form if it is false whenever the overall function is false; in this case, it is called an implicant, because its truth implies the truth of the function. This expression may be made canonical by restricting it to use only prime implicants, the implicants that use a minimal set of variables. The disjunctive normal form using only prime implicants is called the prime DNF. The dual of a Boolean function is obtained by negating all of its variables, applying the function, and then negating the result. The dual of the dual of any Boolean function is the original function. The dual of a monotone function is monotone. 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, this will transform the conjunctive normal form into disjunctive normal form, and vice versa, which may be undesired. Monotone dualization is the problem of finding an expression for the dual function without changing the form of the expression, or equivalently of converting a function in one normal form into the dual form. As a functional problem, monotone dualization can be expressed in the following equivalent ways:
Given a (prime) CNF expression, construct a (prime) CNF expression for the dual function. Convert the (prime) CNF expression of a function into the (prime) DNF expression for the same function, or vice versa Construct the transversal hypergraph of a given hypergraph. This is a hypergraph on the same vertex set that has a hyperedge for every minimal subset of vertices that touches all edges of the given hypergraph. Given a family of sets, generate all minimal hitting sets of the family. These are sets of elements that include at least one element from each set, and have no proper subset with the same property. If the sets in the given family are interpreted as hyperedges in a hypergraph, their minimal hitting sets are the hyperedges of the transversal hypergraph. Given a family of sets, generate all minimal set covers of the family. A set cover is a subfamily with the same union as the whole family. If the sets in the given family are interpreted as vertices in a hypergraph, with each element of the sets interpreted as a hyperedge incident to the sets containing that element, then the minimal set covers are the hyperedges of the transversal hypergraph. Another version of the problem can be formulated as a problem of "exact learning" in computational learning theory: given access to a subroutine for evaluating a monotone Boolean function, reconstruct both the CNF and DNF representations of the function, using a small number of function evaluations. 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. This is because (to be sure of getting the correct answer) the algorithm must evaluate the function at least once for each prime implicate and at least once for each prime implicant, but this number of evaluations can be exponentially larger than the number of prime implicates alone. It is also possible to express a variant of the monotone dualization problem as a decision problem, with a Boolean answer:
Test whether two prime CNF expressions represent dual functions Test whether a prime CNF expression and a prime DNF expression represent the same function.
… excerpt ends here. Continue reading the full article.
