Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables

CSpace

	Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables
	Gao, SX ; Du, DZ ; Hun, XD ; Jia, XH
	2002-06-06
发表期刊	DISCRETE MATHEMATICS
ISSN	0012-365X
卷号	253 期号:1-3 页码:19-34
摘要	A Boolean function f (x(1), x(2),...,x(n)) is elusive if every decision tree computing f must examine all n variables in the worst case. It is a long-standing conjecture that every nontrivial monotone weakly symmetric Boolean function is elusive. In this paper, we prove this conjecture for Boolean functions with twelve variables. (C) 2002 Elsevier Science B.V. All lights reserved.
关键词	monotone Boolean function decision tree elusive
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000176323900004
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/17193
专题	中国科学院数学与系统科学研究院
通讯作者	Du, DZ
作者单位	1.Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA 2.Univ Sci & Technol China, Grad Sch Beijing, Dept Math, Beijing 100039, Peoples R China 3.City Univ Hong Kong, Dept Comp Sci, Kowloon Tong, Hong Kong, Peoples R China 4.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Gao, SX,Du, DZ,Hun, XD,et al. Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables[J]. DISCRETE MATHEMATICS,2002,253(1-3):19-34.
APA	Gao, SX,Du, DZ,Hun, XD,&Jia, XH.(2002).Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables.DISCRETE MATHEMATICS,253(1-3),19-34.
MLA	Gao, SX,et al."Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables".DISCRETE MATHEMATICS 253.1-3(2002):19-34.