399718奇闻趣事网majer 【奇闻趣事网】399718.com07.13 , 20:31
华人学者刚刚解决了布尔函数的敏感度猜想
一位华人学者刚刚解决了敏感度猜想Sensitivity Conjecture，它是理论计算机科学中近三十年来最重要，最令人困惑的开放性问题之一。
鉴于之前评论里有人吐槽说，类似文章全是泛泛而谈的一般科普，核心内容一带而过，就丢出一个399718，所以下面详细说一下敏感度猜想——在汉语网络环境里，相关信息貌似挺少见的。
敏感度猜想，涉及布尔型数据，以及其上的函数关系。
假设x是一个n维数组，其中每个分量都是取值于0或1的布尔数。
假设函数f:{0，1}^n—>{0，1}，亦即定义域是n维数组，同时每个分量都是布尔数；取值也是布尔数。
翻转x第i个分量的值(就是数组中第i个值如果是0，则变成1；是1，则变成0)，得到x_i，如果f(x_i)≠f(x)，就称f对x在第i个分量处敏感。
f对x可能在若干分量处都敏感，记敏感分量的数目为s(f，x)。
当x取遍n维布尔数组后，记s(f，x)的最大值为s(f)。
到此为止，就得到了布尔函数敏感性的定义，但是，猜想本身用到的是布尔函数的块敏感性！
简单说一下，就是上面步骤③里，x_i的角标不再是i，而是集合A，A本身是集合{1,2，……，n}的某个子集。对特定的想，相应的定义，把{1,2，……，n}分化成若干不想交子集，保证f对每个子集都是敏感的。必然有种方式使子集个数最多，子集个数记为相应的bs(f，x)，进一步得到bs(f)。
1994年，数学家Noam Nisan和Mario Szegedy提出了敏感度猜想Sensitivity Conjecture：
存在一个多项式P，对所有的布尔函数f，都成立 bs(f)≤P[s(f)]！
在计算机科学和数理逻辑，乃至代数学里，布尔函数无疑是是否重要的研究对象。同时，我们知道，布尔函数有许多复杂性测度，并且几乎所有这些测度——包括决策树复杂性，证书复杂性，随机查询复杂度和其它许许多多——已知都是多项式相关的。
最新证明的提出者、埃默里大学的数学助理教授Hao Huang向我们解释猜想的价值和意义：“在数学中，布尔函数是最基本的离散主题之一——就像数字，图形或几何形状一样。但是，其它测度都是多项式相关的，而如果猜想为真，则敏感度也是如此，否则的话，它就是很反常的量。”
“自2012年以来，我一直尝试攻克这一猜想。”Huang在接受phys.org采访时说，“但是直到大约一周前，我才捕捉到关键思想。我终于找到了那把正确的钥匙。”
7月15日至19日，将在瑞士苏黎世召开随机结构和算法的国际会议。Huang将在会议上正式发布证明。但是，迫不及待想要了解详情的朋友可以点击此处阅读、下载论文的预印本。
在论文里，Huang先证明n维超立方图的生成子图的相关命题，将猜想作为命题的直接推论。其精巧思路和简单明了的过程，在社交媒体上赢得了计算机科学家和数学家的一片赞誉。
Huang开发出了一种代数方法。“我希望这种方法也有可能应用到对计算机科学的发展至关重要的其他组合和复杂性问题上。”
ps 虽然有人把Hao Huang翻译成了黄浩，但是在埃默里大学的个人主页上，并没有Hao Huang的中文写法。同时我十分确定，在知乎上看到过这位答主，但是也没有找到具体的中文名，所以还是按他主页上的拼音写法为准。
本文版权归原作者，本站只做分享普及使用。若侵犯了你的权益，请提供版权有效证明，核实后下架删除。 (30)
未经允许不得转载：399718奇闻趣事网 » 华人学者刚刚解决了布尔函数的敏感度猜想