华裔数学家用两页纸证明了一个重要的计算机科学猜想

华裔数学家黄皓用两页纸(预印本)证明了一个近 30 年的计算机科学猜想——布尔函数敏感度猜想(Boolean Sensitivity )。证明是如此简洁甚至可以用一条推文概况。敏感度是一种衡量布尔函数复杂度的方法,它被定义为导致布尔函数翻转的最大比特数。Quantamagazine 就此问题举例说:你向银行申请贷款,需要填一系列答案为是或否的问题,银行根据你的答案进行评分做出决定。这个过程就是一个布尔函数,你的答案就是输入比特,银行的决定就是输出比特。如果你改变某个问题的答案会导致结果翻转,这个比特/答案就被定义为敏感了,如果有 7 个问题任意一个翻转会导致结果翻转,那么其敏感度就是 7。

发表评论

电子邮件地址不会被公开。 必填项已用*标注