Lower bounds on the complexity of graph properties
Lower bounds on the complexity of graph properties
复制标题
图属性复杂性的下限
DOI：
10.1145/62212.62258
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
Valerie King
中科院分区：
文献类型：
--
作者：
Valerie King
在这个简单的模型中，决策树算法必须确定节点{1，2，...，n}上的未知有向图是否具有给定的属性，方法是询问“边<i，j>在图中吗？"的问题。财产的复杂性是在最坏的情况下必须提出的问题的数量。
Aanderaa和Rosenberg证明了任何单调的、非平凡的、（同构不变的）n-结点有向图的性质都具有复杂性（<supscrpt>n2</supscrpt>）.<italic></italic>Rivest和Vuillemin证明了该界，并将其改进为<supscrpt>n2</supscrpt>/4+（<supscrpt>n2</supscrpt>）.<italic></italic><italic></italic>在第一部分中，我们给出了<supscrpt>n2</supscrpt>/2+（<supscrpt>n2</supscrpt>）的一个界.<italic></italic><italic></italic>这些属性是否具有规避性仍有待确定。
在第二部分中，我们通过考虑随机决策树算法来研究随机性在识别这些属性中的作用，在随机决策树算法中，硬币可以被翻转以确定要查询的下一个边缘。Yao的关于任意单调非平凡图性质的随机复杂度的下界从（nlog<supscrpt>1/12</supscrpt><italic>n</italic>）改进到（<italic>n5</italic><supscrpt>/4</supscrpt>），并给出了单调非平凡二部图性质的复杂度的改进界.<italic></italic>
In this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes {1, 2, …, n} has a given property by asking questions of the form “Is edge <i,j> in the graph?”. The complexity of a property is the number of questions which must be asked in the worst case.
Aanderaa and Rosenberg conjectured that any monotone, nontrivial, (isomorphism-invariant) n-node digraph property has complexity &OHgr;(<italic>n</italic><supscrpt>2</supscrpt>). This bound was proved by Rivest and Vuillemin and subsequently improved to <italic>n</italic><supscrpt>2</supscrpt>/4+<italic>&ogr;</italic>(<italic>n</italic><supscrpt>2</supscrpt>). In Part I, we give a bound of <italic>n</italic><supscrpt>2</supscrpt>/2+<italic>&ogr;</italic>(<italic>n</italic><supscrpt>2</supscrpt>). Whether these properties are evasive remains open.
In Part II, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next edge to be queried. Yao's lower bound on the randomized complexity of any monotone nontrivial graph property is improved from &OHgr;(<italic>n</italic>log<supscrpt>1/12</supscrpt><italic>n</italic>) to &OHgr;(<italic>n</italic><supscrpt>5/4</supscrpt>), and improved bounds for the complexity of monotone, nontrivial bipartite graph properties are shown.