Polynomial time algorithm for dualizing a monotone DNF

该研究项目的目标是开发一种算法，用于对DNF中给出的布尔函数进行二元化，该算法在输入和输出的总大小中以时间多项式运行。这个问题等价于生成给定超图的所有最小断面的问题。我们无法实现这一最终目标。然而，我们发现了一个算法，用于生成所有的超图的最小断面使用O（n log n）字的存储，其中n是输入超图的大小。该算法的时间复杂度是拟多项式的，几乎与Fredman和Khachiyan提出的算法相同。我们还发现了一个多项式时间延迟算法，用于生成给定的有界度超图的所有最小横截。

The goal of this research project was to develop an algorithm for dualizing a boolean function given in DNF, that runs in time polynomial in the total size of the input and output. This problem is equivalent to the problem of generating all the minimal transversals of a given hypergraph. We were unable to achieve this ultimate goal. However, we discovered an algorithm for generating all the minimal transversals of a hypergraph using O (n log n) words of storage, where n is the size of the input hypergraph. The time complexity of this algorithm is quasi-polynomial and almost the same as the best known algorithm due to Fredman and Khachiyan. We have also discovered a polynomial time delay algorithm for generating all the minimal transversals of a given bounded-degree hypergraph.