New results on monotone dualization and generating hypergraph transversals
New results on monotone dualization and generating hypergraph transversals
复制标题
单调对偶化和生成超图横截面的新结果
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
K. Makino
中科院分区：
文献类型：
--
作者：
Thomas Eiter;G. Gottlob;K. Makino
本文研究了单调CNF的对偶化问题（即计算超图的所有最小截线），其相关的决策问题是np完备性中一个突出的开放问题。我们提出了一些新的多项式时间响应。在重要情况下输出多项式时间结果，这大大提高了可跟踪性边界，并改进了先前的结果。此外，我们证明了两个单调CNFs的对偶性可以用有限的非确定性（更准确地说，在多项式时间内，用$O(log^2 n)$适当猜测位）来证明。这一结果使人们对这个重要问题的复杂性有了新的认识。
This paper considers the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism (more precisely, in polynomial time with $O(log^2 n)$ suitably guessed bits). This result sheds new light on the complexity of this important problem.