A LOWER BOUND FOR THE COMPLEXITY OF MONOTONE GRAPH PROPERTIES

被引：8

作者：

Scheidweiler, Robert ^{[1
]}

Triesch, Eberhard ^{[1
]}

机构：

[1] Rhein Westfal TH Aachen, Lehrstuhl Math 2, D-52062 Aachen, Germany

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2013年 / 27卷 / 01期

关键词：

evasiveness; decision tree complexity; graph properties; RECOGNITION;

D O I：

10.1137/120888703

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

More than 30 years ago, Karp conjectured that all nontrivial monotone graph properties are evasive, i.e., have decision tree complexity ((n)(2)), where n is the number of vertices. It was proved in 1984 by Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297-306] if n is a prime power by a topological approach. Using their method, we prove a lower bound of 1/3 n(2) - o(n(2)) for general n.

引用

页码：257 / 265

页数：9

共 50 条

[1] AN ASYMPTOTIC BOUND FOR THE COMPLEXITY OF MONOTONE GRAPH PROPERTIES
Korneffel, Torsten
Triesch, Eberhard
COMBINATORICA, 2010, 30 (06) : 735 - 743
[2] An asymptotic bound for the complexity of monotone graph properties
Torsten Korneffel
Eberhard Triesch
Combinatorica, 2010, 30 : 735 - 743
[3] An improved lower bound on the sensitivity complexity of graph properties
Sun, Xiaoming
THEORETICAL COMPUTER SCIENCE, 2011, 412 (29) : 3524 - 3529
[4] NEW LOWER BOUND ON THE MONOTONE NETWORK COMPLEXITY OF BOOLEAN SUMS
WEGENER, I
ACTA INFORMATICA, 1980, 13 (02) : 109 - 114
[5] THE CRITICAL COMPLEXITY OF ALL (MONOTONE) BOOLEAN FUNCTIONS AND MONOTONE GRAPH PROPERTIES
WEGENER, I
INFORMATION AND CONTROL, 1985, 67 (1-3): : 212 - 222
[6] THE CRITICAL COMPLEXITY OF ALL (MONOTONE) BOOLEAN FUNCTIONS AND MONOTONE GRAPH PROPERTIES
WEGENER, I
LECTURE NOTES IN COMPUTER SCIENCE, 1985, 199 : 494 - 502
[7] AN OMEGA(N5/4) LOWER BOUND ON THE RANDOMIZED COMPLEXITY OF GRAPH PROPERTIES
KING, V
COMBINATORICA, 1991, 11 (01) : 23 - 32
[8] AN OMEGA(N4/3) LOWER BOUND ON THE RANDOMIZED COMPLEXITY OF GRAPH PROPERTIES
HAJNAL, P
COMBINATORICA, 1991, 11 (02) : 131 - 143
[9] Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution
Lingas, Andrzej
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017), 2017, 10185 : 400 - 410
[10] A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph
Kudo, Taisei
Takemura, Akimichi
JOURNAL OF COMBINATORICS, 2012, 3 (04) : 695 - 708

← 1 2 3 4 5 →