| Abstract: | Decision tree complexity is an important measure of computational complexity.A graph property is a set of graphs such that if some graph G is in the set then each isomorphic graph to G is also in the set.Let P be a graph property on n vertices,if every decision tree algorithm recognizing P must examine at least k pairs of vertices in the worst case,then it is said that the decision tree complexity of P is k .If every decision tree algorithm recognizing P must examine all n(n -1)/2 pairs of vertices in the worst case,then P is said to be elusive .Karp conjectured that every nontrivial monotone graph property is elusive.In this paper,we present some positive results for this conjecture.We research the decision tree complexity of graph property in view of algebraic topology and show that if the abstract simplicial complex of a nontrivial monotone graph property P on n vertices has dimension at most n -1( n -2,in another case),then P is elusive |
