Given is a disjunctive form consisting of k monomials m1, ..., mk over n boolean variables x1, ..., ...

---

Given is a disjunctive form consisting of k monomials m1, ..., mk over n boolean variables x1, ..., xn. The task (Refutation) is to decide whether there is a truth assignment to the variables such that the truth value of the disjunctive form is false. You are given a decision algorithm A_d that solves this problem: for each instance, A_d answers YES if there is an assignment that makes the truth value of the disjunctive form false, and NO otherwise. Describe an algorithm A_o that solves the optimization problem, that is, one that finds a truth assignment making the disjunctive form false if one exists. The running time has to be polynomial in the input size, and A_o may make calls to A_d, where each call counts as one basic computational step.