Complexity of Matroid Property Algorithms
Complexity of Matroid Property Algorithms
复制标题
拟阵属性算法的复杂性
DOI：
--
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
B. Korte
中科院分区：
文献类型：
--
作者：
Per M. Jensen;B. Korte
证明了一个普遍的定理，它可以用来说明对于大量的拟阵性质，没有某种类型的好的算法来确定这些性质是否适用于一般拟阵。具体地说，不存在这样的算法，其中拟阵由独立性测试预言(或与独立性测试预言多项式相关的预言)表示，并且在多次调用由拟阵的基本集合的元素数目中的多项式所限定的预言之后解决所讨论的问题。
A general theorem is proved which can be used to show that for a large number of matroid properties there is no good algorithm of a certain type for determining whether these properties hold for general matroids. Specifically, there exists no algorithm in which the matroid is represented by an independence test oracle (or an oracle polynomially related to an independence test oracle) and which solves the problem in question after a number of calls on the oracle which is bounded by a polynomial in the number of elements of the ground set of the matroid.