Monotone dualization

<p>In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, monotone dualization is a <a href="/facts/Computational_problem/jQ7bYUVh">computational problem</a> of constructing the <a href="/facts/Boolean_algebra/VkCToAmg">dual</a> of a <a href="/facts/Monotonic_function/MjQK0YL2">monotone Boolean function</a>. Equivalent problems can also be formulated as constructing the transversal hypergraph of a given <a href="/facts/Hypergraph/qIR2o2I3">hypergraph</a>, of listing all minimal <a href="/facts/Hitting_set/MVzyBYs1">hitting sets</a> of a <a href="/facts/Family_of_sets/WbYof7lP">family of sets</a>, or of listing all minimal <a href="/facts/Set_cover/MVzyBYs1">set covers</a> of a family of sets. These problems can be solved in <a href="/facts/Quasi-polynomial_time/77T62gmf">quasi-polynomial time</a> in the combined size of its input and output, but whether they can be solved in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> is an open problem.
</p>

Monotone dualization open-in-new

Monotone dualization