solidot新版网站常见问题,请点击这里查看。
数学
wanwan(42055)
发表于2022年05月24日 15时34分 星期二
来自精灵王之女
如果有一百万名计算机科学家共进晚餐,他们会拿到一张巨额账单。如果其中一人特别节俭并且想检查一下账单是否正确,核查过程很简单但会很乏味:他们必须检查账单,一行又一行将所有的单项价格加起来,确保总数等于账单总额。但在 1992 年,六位计算机科学家在两篇 论文中证明可以采用一条激进的捷径。总有一种方法可重新格式化任意长度的账单,只用几个查询可以对其进行检查。更重要的是,他们发现任何计算,甚至是任何数学证明都是如此,因为两者都有自己的收据:计算机或者数学家都必须采取的步骤记录。

这种非常简洁的格式被称为概率可检查证明(PCP)。PCP 已成为理论计算机科学中最重要的工具之一。它们最近甚至进入了实际应用,例如在加密货币中被用于将大批量交易汇总成更容易验证的较小形式。在创建 PCP 之前,计算机科学家已通过类似于晚餐账单检查的解确定了一整类问题——只要你有一个解,就很容易验证。但是对于其中许多问题,先找到一个解要花费的时间似乎长得不切实际。

计算机科学家将这类难以解决但能高效验证的问题命名为 NP。它为许多我们关心的实际问题以及更抽象的问题(例如寻找数学定理的证明)提供了一个概念性的家园。求解是一步一步地求证,建立起绝对确定的数学结论——就像逐项汇总账单证明总额一样。求解可能会很难,但是一旦你有了一个解,就可以直接进行检查。这类证明就完全属于 NP 的范畴
数学
wanwan(42055)
发表于2022年05月18日 15时01分 星期三
来自太空战
Leslie Lamport 的名字可能不是家喻户晓,但作为计算机科学家,他比起那些名人不遑多让:排版程序 LaTeX 以及让 Google 和亚马逊云基础设施成为可能。他对一些问题给予了更多的关注,给它们起了独特的名字,比如面包店算法和拜占庭将军问题。这绝非偶然。这位 81 岁的计算机科学家对于人们如何使用和看待软件有着不同寻常的深入思考。2013 年,他赢得了被认为是计算领域诺贝尔奖的A.M.图灵奖,以表彰他在分布式系统方面的工作,此类系统由不同网络上的多个组件相互协调实现共同目标。互联网搜索、云计算和人工智能都涉及编排强大的计算机军团协同工作。当然这种协调也会给你带来更多的问题。Lamport曾说过:“分布式系统是这样一个系统:一台你甚至不知道其存在的计算机出现故障,就可能导致你自己的计算机无法使用。”

问题的最大来源之一是“并发系统”,其中多个计算操作发生在重叠的时间片中,导致模棱两可:哪台计算机的时钟是正确的?在 1978 年的一篇开创性论文中,Lamport 借鉴狭义相对论的见解,引入了“因果关系”概念解决这个问题。两个观察者可能在事件的顺序上存在分歧,但如果一个事件导致另一个事件,这就消除了分歧。并且发送或接收消息可以在多个进程之间建立因果关系。逻辑时钟——现在也称为 Lamport 时钟——提供了一种推理并发系统的标准方法。有了这个工具,计算机科学家接下来想知道他们如何能系统地使这些联网计算机变得更大,而不会增加错误。Lamport 提出了一个优雅的解决方案:Paxos,一种允许多台计算机执行复杂任务的“共识算法”。如果没有 Paxos 及其算法家族,现代计算就不可能存在。
数学
wanwan(42055)
发表于2022年04月26日 16时58分 星期二
来自火星超人
数学家 Jeff Kahn 和 Gil Kalai 在 2006 年首次提出“期望阈值”猜想时,他们自己都不相信。他们声称——对名为随机图的数学对象的广泛论断——似乎太强大、太包罗万象,也太大胆,所以不可能是真的。这更像是一种一厢情愿的想法,而不是数学真理。即便如此,没人能证明它是错误的,它很快成为该领域最重要的开放问题之一。15 年多时间过去了,斯坦福大学的一对年轻的数学家完成 了 Kahn 和 Kalai 认为不可能做到的事情:在几周前发布在网上的一份令人惊讶的简短预印本论文中,Jinyoung Park 和 Huy Tuan Pham 给出了对该猜想的完整证明。这一成果自动证明了数以百计更具体的陈述,每一种陈述都很难单独证明——且它对我们更广泛地理解随机图和数学集有更深层次的影响。Kahn-Kalai 猜想非常广泛——它是用集合及其元素的抽象语言写成的——但是可通过简单的例子理解它。首先,想象一张图:一组由线或边连接的点或者顶点。要制作随机图,请取出一枚偏币(biased coin)——一个落下来有 1%、30% 或者是 0 到 100 之间任意百分比概率正面朝上的硬币——然后针对给定的一对定点掷一次硬币。如果硬币落下来是正面朝上,就将这两个点用边线连接起来;如果硬币反面朝上,就不要这样做。对每一对可能的顶点都重复这个过程。
数学
wanwan(42055)
发表于2022年04月21日 15时12分 星期四
来自爱的左边
MIT 的一个机械工程师团队开发出“奥利奥表(Oreometer)”,测试将奥利奥饼干分成两片并保持饼干和里面的奶油夹心完好无损的最优方法。这是一项流变学的试验,流变学是对物质如何流动的研究。研究人员将这个特殊的试验称为“奥利奥学(Oreology)”。在试验中,流体是奶油夹心,一种被该团队归类为“糊状”的柔软固体,这意味着它不是很脆(不像饼干)并且相对柔软(就像面包)。研究团队构建了 Oreometer 测试如何分离不同类型的奥利奥饼干,特别关注两片饼干分开之后奶油夹心的分布。他们的研究报告发表在《流体物理学》上。

论文主要作者、MIT 机械工程师 Crystal Owens 表示:“我们最喜欢的扭转方式是在旋转的同时将奥利奥从一侧拉开,作为一种扭转剥离的方法,这是将饼干干净利落分开最可靠的途径。”“众所周知,剥离会导致粘合剂失效,如果你想从表面撕下贴纸又不想破坏贴纸本身的话。”研究人员们发现,奶油夹心通常会留在一边的饼干(“饼干1”)而不是另一边的饼干上,他们认为这是由于奥利奥的制造方式造成的。他们测试了普通的奥利奥和带有更多奶油夹心的 Double 和 Mega Stuf 品种,报告未提及奶油夹心含量与分开之后的饼干干净程度之间存在任何明显的相关性。他们开源了 Oreometer 的设计,因此任何人都可以造出自己的装置,并收集关于将奥利奥饼干分开或切开的数据。小朋友会感到自豪的
数学
WinterIsComing(31822)
发表于2022年04月21日 14时27分 星期四
来自小无知游太阳城(上下)
清华大学宣布,菲尔兹奖首位华人得主丘成桐从哈佛大学退休,受聘清华大学讲席教授。这意味着丘成桐将全职任教清华丘成桐于 1949 年出生在广东汕头,几个月大时与全家移民香港,1966 年入读香港中文大学崇基学院数学系,三年内修毕四年课程,被加州伯克利破格录取为研究生,师从陈省身。丘成桐于 22 岁时取得博士学位,25 岁被聘为斯坦福大学教授。1976 年 27 岁的丘成桐证明了困扰数学界 22 年之久的卡拉比猜想,推动微分几何新时代的到来。1979 年他与学生 Richard Schoen 合作解决了爱因斯坦广义相对论中的正质量猜想。33 岁时丘成桐获得数学界最高奖菲尔兹奖,是首位获此殊荣的华人。
数学
WinterIsComing(31822)
发表于2022年04月01日 22时11分 星期五
来自记忆残留
根据发表在《Scientific Reports》期刊上的一项动物行为研究,斑马拟丽鱼(慈鲷鱼的一种)和公式鱼能完成 1 到 5 以内加减 1 位的计算。科学家认为,研究结果表明,鱼的算术能力和其它脊椎动物及无脊椎动物的算术能力不相上下。研究人员发现,有 6 条斑马拟丽鱼和 3 条公式鱼通过训练记住了蓝色和加法以及黄色和减法的关系。平均而言,斑马拟丽鱼在28个回合、公式鱼在68个回合后能记住这些关系。鱼在这类任务中的表现一般都很好,但加法学起来比减法更快,而且斑马拟丽鱼的个体差异比公式鱼更大一些。在加法任务中,斑马拟丽鱼在 381 次测试中正确了 296 次(78%),公式鱼在 180 次测试中正确了 169 次(94%)。在减法任务中,斑马拟丽鱼在 381 次测试中正确了264次(69%),公式鱼在 180 次测试中正确了 161 次(89%)。研究人员认为,计算能力可以帮助这两个物种通过外观辨认其他个体,比如数一下鱼身体上的条纹或斑点。研
数学
WinterIsComing(31822)
发表于2022年03月23日 21时35分 星期三
来自星际归途
2022 年度阿贝尔奖授予了 81 岁的美国纽约数学家 Dennis P. Sullivan,以表彰他在拓扑学尤其是代数拓扑和拓扑动力系统上的突出贡献。阿贝尔奖奖金与诺贝尔奖相近。它与菲尔兹奖齐名,后者主要吸引年轻人从事数学研究,一起扩大数学的影响是设立阿贝尔奖的主要目的。Sullivan 博士听到这一消息之后说他 81 岁了,还有人记得他。他将得到大约 85 万美元奖金。Sullivan 博士的工作涉及到的是拓扑学中的流形
数学
wanwan(42055)
发表于2022年02月28日 17时48分 星期一
来自歌剧院魅影
我们经常认为乘法和除法是需要学校教授的计算。但一项大型研究表明,即使是在接受正规教育之前,儿童就具有直觉的算数能力。发表在《人类神经科学前沿》期刊上的新研究认为,这种进行近似计算的能力甚至延伸到了最“可怕”的基本数学问题——真正的除法,影响学生未来如何学习数学概念。研究的基础是近似数字系统(ANS),这种理论认为人类(甚至还有非人类灵长类动物)从小就有一种直觉式的能力,无需依赖语言或者符号,就能比较和估计大量的对象。例如在非符号系统中,儿童可以识别出 20 个点的一组大于 4 个点的一组——哪怕这 4 个点在纸上占据了更大的空间。做出更精确近似的能力——比如说比较 20 个点和 17 个点——会在成年期发展出来。
数学
matrix(791)
发表于2022年01月14日 19时25分 星期五
来自开普罗纳的魔法师
黎曼(Bernhard Riemann)提出关于素数分布的开创性猜想之后,162 年过去了。尽管尽了最大努力,数学家在证明黎曼猜想上取得的进展很小。但他们设法在一个相对简单的相关问题上取得了进展。在 9 月发表的一篇论文中,高等研究院的 Paul Nelson 解决了亚凸界问题(subconvexity problem),这是黎曼猜想的一种轻量级版本。证明本身是一项重大成就,让人们期待与素数相关的更大发现。Nelson 表示:“这是一个有点牵强的梦想,但是你可以非常乐观地希望,也许我们可以研究这样的问题来了解黎曼猜想是怎么回事。”黎曼假设和亚凸界问题很重要,因为素数是数学中最基本的——也是最神秘的对象。当你将它们放在数轴上时,其分布方式似乎没有规律。但在1859 年,黎曼设计了名为黎曼 zeta 函数的对象——一种无限和——它推动了一种革命性的方法,如果得到证明,它将揭开素数的隐藏结构。证明它几年前还被视为是科幻故事。
数学
wanwan(42055)
发表于2022年01月11日 18时22分 星期二
来自白鸟异传
1779 年瑞士数学家欧拉(Leonhard Euler)提出了一个后来闻名遐迩的难题:有六个军团,每个军团都有六名军衔不同的军官。是否可以将这 36 名军官排成一个6×6的方队,让方队每行每列中的军官所属的军团和军衔都各不相同。

如果是五个军团和五种军衔,或者是七个军团和七种军衔,这个难题容易解决。在为 36 名军官的情况寻找解决方案无果之后,欧拉得出结论:“这种排列是不可能实现的,尽管无法给出严格的证明。”一个多世纪后,法国数学家 Gaston Tarry 证明,确实没有办法将欧拉的 36 名军官排列在一个 6×6 的方队中而不重复。1960 年,数学家使用计算机证明,只要军团和军衔数量是大于 2 的任何数字,解决方案就存在,但奇怪的是——6 除外。

2000 多年来,类似的谜题一直吸引着人们。世界各地的文化中都有“幻方”,即让每行和每列上所有数字相加的和都相等的数字方阵,以及“拉丁方阵(Latin squares)”,即每个符号在每行和每列中都出现一次。这些方阵被用于艺术和城市规划,也被人们娱乐。一种流行的拉丁方阵——数独——要求子方格中也没有重复的符号。欧拉的 36 名军官的谜题要求一个“正交的拉丁方阵”,其中两种属性——军衔和所属军团要同时满足拉丁方阵的规则。

尽管欧拉认为不存在这样的 6×6 方队,但游戏最近有了改变。在网上发布并提交给《物理评论快报》的一篇论文中,印度和波兰的一组量子物理学家证明,可以以符合欧拉标准的方式安排 36 名军官——只要这些军官拥有军衔和军团的量子混合。这是开发量子版本幻方和拉丁方阵工作的最新成果,这不仅是为了娱乐和游戏,还可以应用于量子通信和量子计算。
数学
wanwan(42055)
发表于2022年01月05日 17时47分 星期三
来自钻石
一项新证明驱散了数学家担心可能会笼罩数轴的阴云。它提供了另一套工具理解算术的基本结构单元——素数。在去年 3 月发表的一篇论文中,德国哥廷根大学的 Harald Helfgott 和加州理工学院的 Maksym Radziwiłł 提出了一个改进的解决方案,可以解决 Chowla 猜想的特定公式,Chowla 猜想是一个关于整数之间关系的问题。该猜想预测一个整数是否有偶数或奇数个素因数,并不影响后一个或前一个整数是否也有偶数或奇数个素因数。也就是说相邻的数字不会共有一些最基本的算术属性。

这种看似简单的探究与数学中关于素数本身的一些最深层次的未解难题交织在一起。加州大学洛杉矶分校的陶哲轩表示,证明 Chowla 猜想是回答那些更棘手问题的“某种热身或垫脚石”。然而几十年来,“热身”本身就成了一项几乎无可能完成的任务。几年前数学家取得了些许进展,陶哲轩当时证明了对数 Chowla 猜想,它是该问题的一个简单版本。虽然他使用的技术被誉为颇具创新性并令人兴奋的,但是它产生的结果不够精确,对在相关问题(包括素数问题)上取得更多进展没什么帮助。数学家盼望能有一个更强大、更广泛适用的证明。现在 Helfgot t和 Radziwiłł 实现了这一点。他们的解决方案将图论中的技术直接引入数论的核心,重新点燃了证明 Chowla 猜想的希望——最终引导数学家找到解决一些最难以捉摸问题所需要的思路。
数学
wanwan(42055)
发表于2021年12月22日 17时20分 星期三
来自独眼巨人的笑声
两项新研究表明,虚数对于准确描述现实是必要的。虚数是负数取平方根后得到的数,绝大多数重要的量子力学方程都需要使用虚数,量子力学是物理学描述微观世界的一个分支。当你将虚数和实数相加时,两者形成复数,这使物理学家能用简单的术语写出量子方程。但量子理论是否需要这些数学嵌合体,还是只是为了方便,这个问题长期以来一直存在着争议。事实上,即使是量子力学的创始人自己也认为在他们的方程中包含复数的含义令人不安。物理学家薛定谔(Erwin Schrodinger)用量子波函数第一次将复数引入量子理论,在写给他的朋友洛伦兹(Hendrik Lorentz)的一封信中,他写道:“复数的使用在这里令人不快,实际上是被直接反对的。量子波函数从根本上说肯定是一个实函数。”

薛定谔确实找到了方法,用实数和一组如何使用方程的额外规则表达方程,后来的物理学家也对量子理论的其他部分做了相同的事情。但是在没有确凿的实验证据来证明这些“全实数”方程预测的情况下,一个问题一直存在:虚数是一种可选的简化,还是试图在没有它们的情况下工作会剥夺量子理论描述现实的能力?现在 12 月 15 日发表在《自然》和《物理评论快报》期刊上的两项研究证明薛定谔是错误的。通过一个相对简单的实验,他们表明如果量子力学是正确的,虚数就是我们宇宙数学的必要组成部分。论文的主要作者、西班牙光子科学研究所的理论物理学家 Marc-Olivier Renou 表示:“量子力学的早期创始人找不到任何方法解释理论中出现的复数。”“复数用起来很好,但是没有明确的方法来确定具有现实元素的复数。”为了测试复数是否具有现实重要性,第一项研究的作者对被称为贝尔试验的经典量子实验进行少许设计上的调整。贝尔试验由物理学家 John Bell 在 1964 年首次提出,目的是证明量子理论要求的量子纠缠——两个相距遥远的粒子间的奇怪联系,爱因斯坦(Albert Einstein)反对这一观点,称其为“鬼魅般的超距作用”。
数学
wanwan(42055)
发表于2021年12月16日 15时53分 星期四
来自沙皇的邮件
牛津大学数学家 Ben Green 在理解一个百年前组合数学问题方面取得重大进展,表明一个著名的猜想,正如蒙特利尔大学的 Andrew Granville 所说,“不仅错了而且错得离谱”。新论文展示了如何创建超过数学家认为可能的长度的无序彩色珠串,拓展了 1940 年代以来的一系列工作,这些工作已应用于计算机科学等领域。

Ron Graham 是过去半个世纪顶尖的离散数学家之一,这个猜想是他在 17 年前提出的:你可以将多少蓝色和红色的珠子串在一起,而又不会创造任何长序列间隔均匀的单色珠子。(你可以决定对于每种颜色来说这个“长”有多长。)

这是拉姆齐理论最古老的问题之一,探讨在必然出现有序之前,各种数学对象可增长到多大。珠串问题说起来容易,实际上却很难:对于长串,珠串可能的排列方式多到无法一一尝试。 斯坦福大学的 Jacob Fox 表示:“有时我们对一些看似非常基本的问题真的几乎一无所知。很多人会惊讶于我们对一些问题所知甚少,这个问题就是其中之一。”

近一个世纪以来,数学家都知道你不能无限地串珠子。一旦你为每种颜色选好了参数,在被迫创建超出你忍受范围的均匀间隔序列之前,你就只能串接这么多的珠子。如果你提高红色和蓝色的参数,可串接的珠子的总数会增加——但是增加的速度有多快?

在这个问题的一个版本中,你禁止最短的均匀间隔的蓝色序列出现,Graham 推测(PDF)会有一个简单的关系成立:可能的、最长的珠串长度大约是红色珠子参数的平方。所有数学家积累的数据资料都支持 Graham 的这一猜想。

但现在 Green 证明这个猜想是错误的。在长达 68 页的论文中,他展示了如何制作比 Graham 预测的长得多的珠串。Green 融合了几何和动力系统创建无序珠串,他的结构建立早期的珠串结构之上,这种早期珠串结构应用在从矩阵乘法到密码学的各个学科中。Fox 表示,这种结构“对计算机科学中的一些问题非常重要。”
数学
wanwan(42055)
发表于2021年12月10日 20时47分 星期五
来自炼金术战争:解放
在 3 月发表的一篇近 400 页的论文中,哥伦比亚大学的数学家 Mohammed Abouzaid 和 Andrew Blumberg 大幅拓展了几何学近几十年以来最大的进步之一。他们所做的工作与 Vladimir Arnold 在 1960 年代提出的一个著名的猜想有关。Arnold 当时研究经典力学,他想知道行星的轨道何时能稳定,在一段时间之后恢复到初始状态。

Arnold 的工作涉及物理系统如弹跳台球或绕轨道运行的行星可采用的所有不同配置。这些配置被编码在称为相空间的几何对象中,在被称为辛几何的数学领域具有重要作用。Arnold 预测,特定类型的每个相空间都包含最少量的配置,在这些配置中,它所描述的系统返回到它开始的地方。这就像台球会占据与先前相同的位置和速度。他预计这个最小数量至少等于整个相空间中孔的数量,它可以采取球体(没有孔)或者甜甜圈(有一个孔)等物体的形式。Arnold 猜想将两种完全不同的形状思考方式联系起来。它表明就其柔软的拓扑特性(它有多少个孔)而言,数学家可以获得关于物体在给定形状下的运动信息(反映在有多少配置让物体返回到它开始的地方)。斯坦福大学的 Ciprian Manolescu 表示:“通常来说,辛比纯拓扑更难。因此能从拓扑信息中分辨出辛是关键。”

Arnold 猜想的第一个重大进展出现在 1980 年代,当时名叫 Andreas Floer 的年轻数学家开发了一种全新的孔洞计算方法。Floer 的理论很快就成了辛几何的核心工具之一。然而即使数学家使用了 Floer 的想法,他们还是认为按照 Floer 开辟的新视角,应该有可能超越理论本身发展出其他的理论。Abouzaid 和 Blumberg 做到了。在 3 月份的论文中,他们根据 Floer 开创的孔洞计算技术重新构建了另一个重要的拓扑理论。他们用这种新的理论来证明 Arnold 猜想的一个版本,呼应了 Floer 的工作。早期的概念验证结果让科学家期待他们终将发现 Abouzaid 和 Blumberg 的想法的更多用途。
数学
wanwan(42055)
发表于2021年11月18日 17时26分 星期四
来自量子之夜
一个国际数学家团队发表了边界层湍流的完整描述。该团队由加州大学圣巴巴拉分校的 Björn Birnir 教授和奥斯陆大学的 Luiza Angheluta 教授领导。论文发表在《Physical Review Research》期刊上,综合了该主题数十年的工作。该理论将经验观察与 Navier-Stokes 方程——流体动力学数学基础——结合成一个数学公式。

边界层湍流于 1920 年左右由匈牙利物理学家 Theodore von Kármán 和德国物理学家 Ludwig Prandtl 首次描述,两人都是流体动力学领域的杰出人物。复杂与非线性科学中心主任 Birnir 表示:“他们研究的是今天称为边界层湍流的现象”。这种现象是当流体与边界(例如流体表面、管壁、地球表面等)相互作用时引起的湍流。

Prandtl 通过实验发现可根据与边界接近的程度将边界层划分为四个不同的区域。粘性层在边界附近形成,湍流被流动的厚度减弱。接着是过渡缓冲区,其次是惯性区,湍流发展得最充分。最后根据 von Kármán 的公式,尾流是边界层流动受边界影响最小的地方。

流体离边界越远流动越快,但其速度以非常特定的方式变化。它的平均速度在粘性层和缓冲层中增加,然后在惯性层中转变为对数函数。Prandtl 和 von Kármán 发现的这种“对数定律”让研究人员感到困惑,他们努力了解它的来源以及如何描述它。

流动的变化——或与平均速度的偏差——也显示出跨越边界层的特殊行为。研究人员试图了解这两个变量并推导出可以描述它们的公式。
数学
wanwan(42055)
发表于2021年11月02日 17时44分 星期二
来自龙岛
我们的生活是一连串的优化问题。当我们寻找下班回家的最快路线或在去商店的路上试图平衡成本和质量时,甚至当我们决定如何度过睡前有限的空闲时间时,就会出现此类问题。 这些场景和许多其他场景可以表示为数学优化问题。做出最佳决策就是找到最优解。对于一个沉浸在优化中的世界,最近的两项研究成果既带来了好消息也带来了坏消息。 在 2020 年 8 月发表的一篇论文中,普林斯顿大学的 Amir Ali Ahmadi 和他以前的学生、现就读于卡内基梅隆大学的 Jeffrey Zhang 确定,对于一些二次优化问题(这类问题中成对的变量会相互作用),在计算上以具有时效性的方式即使是寻找局部最优解也是不可行的。 但是两天之后,Zhang 和 Ahmadi 发表了第二篇论文,给出了积极的结论。他们证明,快速确定三次多项式(变量之间存在三向相互作用)是否存在局部最小值并找到这个值(如果存在的话)总是可行的。
数学
wanwan(42055)
发表于2021年10月28日 20时18分 星期四
来自霸主的影子
P vs NP 问题被视为理论计算机科学和数学领域最重要的问题,但解决该问题被认为完全遥不可及。它旨在解决计算的前景、极限和目标的核心问题,即:

为什么有些问题比其他问题更难?
计算机可以实际解决哪些问题?
需要多少时间?

这是一项具有重大哲学和实践回报的探索。德州奥斯丁的计算机科学家 Scott Aaronson 在他的思想回忆录《Quantum Computing Since Democritus》中写道:“看,这个P vs NP的问题,我还能说什么?人们喜欢将其描述为‘可能是理论计算机科学中尚未解决的核心问题。’这是一种轻描淡写的可笑说法。P vs NP 是人类曾经提出过的最深刻的问题之一。”可以用这种方式理解这个问题:“P”代表计算机可以轻松解决的问题。“NP” 代表一旦解决就很容易检查的问题,比如拼图游戏或数独游戏。许多 NP 问题对应的是社会面临的一些最顽固和最紧迫的问题。价值百万美元的 P vs. NP 问题是:这两类问题是同一类吗?也就是说如果能找到正确快速的算法,那么看起来如此困难的问题实际上能在合理的时间内用算法解决吗?如果是这样,许多难题突然就可解了。它们的算法解决方案可以带来乌托邦式的社会变革——在医学、工程和经济学、生物学和生态学、神经科学和社会科学、工业、艺术、甚至政治等领域。
数学
WinterIsComing(31822)
发表于2021年10月11日 13时30分 星期一
来自其主之声
互联网梅森素数大搜索(GIMPS)项目宣布第 48 个梅森素数 M(57 885 161)已正式获得验证。M(57 885 161) 是在 2013 年发现的,M(82 589 933) 是在 2018 年 12 月 7 日发现的,是第 51 个也是最新的梅森素数。GIMPS 是一个分布式计算项目,创建于 1996 年,至今已有 25 年历史,它利用志愿者的空闲 CPU 创建了一个遍布全球的超级计算机。
数学
wanwan(42055)
发表于2021年09月16日 16时10分 星期四
来自魔法集成
在任意特定时刻碰巧身处城市中心的人群似乎只是个随机集合,但使用简单数学定律得出的最新研究成果表明,实际上全球各个城市的出行模式都具有极强的可预测性——这一见解不仅可以增强疾病传播建模,同时也有助于优化城市规划。通过研究匿名手机数据,研究人员发现城市中特定位置的人数与他们到达那里的距离以及出行频率之间呈平方反比关系。从直觉上说人们会倾向于前往附近的地点、而很少选择距离较远的区域;但这项最新发现的关系将基本概念转化成了特定数字表达。例如它能准确预测出每周从 2 公里以外前来的人数会 5 倍于每周从 5 公里以外前来的人数。研究人员的这种新计算方法以及由此建立的市内个人流动通用模型已经被刊登在《自然》杂志上。

研究人员分析了 2006 年至 2013 年六个城市区域总计约 800 万民众的数据,具体涵盖波士顿、新加坡、里斯本、葡萄牙的波尔图、塞内加尔的达喀尔以及象牙海岸的阿比让。之前的分析主要使用手机数据来研究个人出行路径,但这一次的研究则重点关注地理区域,具体跟踪有多少人前来、距目的地多远、访问频率如何等。研究人员发现,从接送孩子到购物或通勤,人们做出的每一次选择都会无意中综合考量这个平方反比定律。对这种强统计模式的一种解释在于,出行所耗费的时间与精力对每个人来说都是一种有限的资源。
数学
wanwan(42055)
发表于2021年09月15日 16时46分 星期三
来自奥泊城的珍宝
想象一下假如你是一名古代的将军,既想清点三军又不希望人数被敌方察觉。到底该怎么实现?只需小小的数学技巧就能帮我们解决问题。在晨练中,我们要求士兵排成五行,并注意到最后一行只有三名士兵。之后重新排成八行,最后一行有七名士兵。之后是排成九行,最后一行是两名士兵。虽然没有具体清点,但我们已经掌握了充足的信息,完全可以在敌方毫无知觉的情况下知晓己方人数。从传说故事来看,中国古代的将军似乎确有使用这种精妙的点兵技巧。这种方法被称为中国剩余定理,可能由中国数学家孙子在公元 3 世纪到 5 世纪之间发现(与写孙子兵法的孙子不是同一个人)。该定理约定:只要我们知道某个未知数除以某些“成对互质”数时的余数(即二者不存在任何共同的质因数),即可求出此未知数本身。孙子虽然没有对此做出正式证明,但后来的印度数学家及天文学家 Aryabhata 给出了具体过程,彻底解决了此定理的任何给定实例。佐治亚大学的 Daniel Litt 表示,“中国剩余定理确实给出了真实有效的计算方法。”