Polynomial time algorithm for dualizing a monotone DNF

本研究项目的目标是开发一种算法，用于对DNF中给定的布尔函数进行对偶化，该算法以输入和输出的总大小为时间多项式运行。这个问题等价于生成给定超图的所有最小截线的问题。我们没能达到这个终极目标。然而，我们发现了一种算法，可以使用O （n log n）个存储字来生成超图的所有最小截线，其中n是输入超图的大小。该算法的时间复杂度为拟多项式，与Fredman和kachiyan提出的最著名的算法几乎相同。我们还发现了一个多项式时间延迟算法，用于生成给定有界度超图的所有最小截线。

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.