Monotone dualization

The problem of finding the prime CNF expression for the dual function of a monotone function, given as a CNF formula, can be solved by finding the DNF expression for the given function and then dualizing it. Therefore, finding the dual CNF expression, and finding the DNF expression for the (primal) given function, have the same complexity. This problem can also be seen as a special case of the exact learning formulation of the problem. From a given CNF expression, it is straightforward to evaluate the function that it expresses. An exact learning algorithm will return both the starting CNF expression and the desired DNF expression. Therefore, dualization can be no harder than exact learning.[5]

It is also straightforward to solve the decision problem given an algorithm for dualization: dualize the given CNF expression and then test whether it is equal to the given DNF expression. Therefore, research in this area has focused on the other direction of this equivalence: solving the exact learning problem (or the dualization problem) given a subroutine for the decision problem.[4]

Bioch & Ibaraki (1995) outline the following algorithm for solving exact learning using a decision subroutine:

• Initialize sets of the prime CNF and prime DNF clauses that have been identified so far, initially empty.
• Repeat the following steps:
  • Use the decision problem to test whether the current sets of prime CNF and prime DNF clauses are dual, and if so terminate the algorithm, returning the clauses that have been found.
  • Construct a truth assignment to the variables for which the function value is neither forced to be true by the known prime DNF clauses, nor forced to be false by the known prime CNF clauses. This construction may be performed by choosing values for the variables one at a time, at each step using the decision problem to preserve the property that the CNF and DNF clauses are non-dual when restricted to the chosen truth assignment.
  • Evaluate the function at this truth assignment. If it is true, then try changing variables one at a time from true to false to find a minimal truth assignment for which the function still evaluates as true. This minimal truth assignment corresponds to a prime DNF clause, not already known; add this to the set of known clauses.
  • Symmetrically, if the function evaluates to false, then try changing variables one at a time from false to true to find a maximal truth assignment for which the function still evaluates as false. This maximal truth assignment corresponds to a prime CNF clause, not already known; add this to the set of known clauses.

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. Therefore, the total number of calls to the decision problem and the total number of function evaluations is a polynomial of the total output size.[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.[1][6] Their algorithms directly solve the decision problem, but can be converted to the other forms of the monotone dualization problem as described in § Equivalence of different formulations. 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. Its main idea is to first "clean" the decision problem instance, by removing redundant information and directly solving certain easy-to-solve cases of the problem. Then, in remaining cases it branches on a carefully chosen variable. This means recursively calling the same algorithm on two smaller subproblems, one for a restricted monotone function for which the variable has been set to true and the other in which the variable has been set to false. 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]

• Remove any clause that is not minimal among the given set of clauses. (That is, the removed clause uses a set of variables that is a superset of the variables in another clause of the same type.)
• If the two sets of clauses (CNF and DNF in one version of the decision problem, or sets of CNF clauses that are supposed to represent two dual functions in another version) do not cover the same sets of variables, return that they are not dual.
• If two clauses from different sets of clauses use disjoint sets of variables, return that they are not dual. In this case, the clauses imply contradictory function values for any truth assignment that is consistent with both of them.
• If any clause in one class uses a number of variables that is larger than the number of clauses in the other class, return that they are not dual. If this clauses is to be minimal, it cannot be the case that removing any one variable from it produces a valid clause for the same function, but there are not enough clauses from the other class to block each of these removals.
• For each clause, count the number of truth assignments whose function value is determined by the clause. This number is ${\displaystyle 2^{n-k}}$, for a clause with ${\displaystyle k}$ variables in a problem with ${\displaystyle n}$ variables. If the sum of these numbers, added over all clauses of both types, is fewer than the ${\displaystyle 2^{n}}$ truth assignments that exist in total, then return that the two sets of clauses are not dual: at least one truth assignment must have a value that they do not determine.
• If either set of clauses is empty, or both consist of only one clause, handle the problem as a special case in constant time.
• In the remaining cases there exists a variable which occurs in a large fraction of one of the two sets of clauses. Branch on that variable. More precisely, if there are ${\displaystyle m}$ total clauses, then (to cover all of the truth assignments) at least one of the clauses must have at most ${\displaystyle \log _{2}m}$ variables. Each clause in the other set of clauses must have a non-empty intersection with this short clause, so one of the variables in the short clause occurs in at least a ${\displaystyle 1/\log _{2}m}$ fraction of the other set of clauses.

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 ${\displaystyle (\log n)^{3}}$.[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. If that recursive call fails to find an inconsistency, then, instead of performing a single recursive call for the other branch, it performs one call for each clause that contains the branch variable, on a restricted subproblem in which all the other variables of that clause have been assigned in the same way. Its running time is an exponential function of ${\displaystyle (\log n)^{2}}$.[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:

• Dualization of CNF or DNF formulas in which each variable appears in a bounded number of clauses,[7] or exact learning of monotone functions that have formulas of this type.[8]
• Constructing transversal hypergraphs of uniformly sparse hypergraphs, in which every induced sub-hypergraph has bounded average degree,[9] and of hypergraphs for which generalizations of the graph-theoretic concepts of treewidth or degeneracy are bounded.[10]
• Constructing transversal hypergraphs for which the complement (the hypergraph obtained by complementing each hyperedge) has low degree.[11]