Monotone Bipartite Graph Properties are Evasive

Autor:	Andrew Chi-Chih Yao
Rok vydání:	1988
Předmět:	Combinatorics Discrete mathematics Vertex (graph theory) Monotone polygon General Computer Science Aanderaa–Karp–Rosenberg conjecture General Mathematics Prime number Bipartite graph Computer Science::Computational Complexity Boolean function Logical Function Mathematics
Zdroj:	SIAM Journal on Computing. 17:517-520
ISSN:	1095-7111 0097-5397
DOI:	10.1137/0217031
Popis:	A Boolean function P from $\{ {0,1} \}^\prime $ into $\{ {0,1} \}$ is said to be evasive, if every decision-tree algorithm for evaluating P must examine all t arguments in the worst case. It was known that any nontrivial monotone bipartite graph property on vertex set $V \times W$ must be evasive, when $|V| \cdot |W|$ is a power of a prime number. In this paper, we prove that every nontrivial monotone bipartite graph property is evasive.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::630923c45db6edd134dfc75a1021ad27 https://doi.org/10.1137/0217031 Zobrazit plný text záznamu