[导读]P≠NP,一个简洁的论文标题,或许预示着七大世界数学难题之一的P问题(多项式算法)对NP问题(非多项式算法)终于有了答案。据英国《新科学家》杂志网站8月11日(北京时间)报道,美国惠普实验室的数学家维奈
P≠NP,一个简洁的论文标题,或许预示着七大世界数学难题之一的P问题(多项式算法)对NP问题(非多项式算法)终于有了答案。据英国《新科学家》杂志网站8月11日(北京时间)报道,美国惠普实验室的数学家维奈·迪奥拉里卡已经于6日提交了关于论证该问题的论文草稿,如果此答案被证实无误,那么他将获得由美国克雷数学研究所提供的100万美元奖金。
P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一,同时也是计算机科学领域的最大难题,关系到计算机完成一项任务的速度到底有多快。有些问题计算起来很容易,利用多项式算法很快能解决,比如求若干个数的乘积,这类问题被称作P问题;另一类问题计算过程比较繁琐,但验证答案却很容易,比如把整数44427进行因数分解,求解过程可能会很费时,但如果告诉你答案是177×251,简单计算即可验证答案是对的,这类问题就被归为NP问题。
因此,如果P=NP,那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计算机安全构成巨大威胁,目前加密系统的破解就相当于要将一个整数分解为几个因数的乘积,正是其求解过程的繁琐,才能杜绝黑客的入侵。
而现在,迪奥拉里卡围绕一个众所周知的NP问题进行论证,给出了P≠NP的答案。这就是布尔可满足性问题(Boolean Satisfiability Problem),即询问一组逻辑陈述是否能同时成立或者互相矛盾。迪奥拉里卡声称,他已经证明,任何程序都无法迅速解答这个问题,因此,它不是一个P问题。
如果迪奥拉里卡的答案成立,说明P问题和NP问题是不同的两类问题,这也意味着计算机处理问题的能力有限,很多任务的复杂性从根本上来说也许是无法简化的。
对于有些NP问题,包括因数分解,P≠NP的结果并没有明确表示它们是不能被快速解答的;但对于其子集NP完全问题,却注定了其无法很快得到解决。其中一个著名的例子就是旅行商问题(Travelling Salesman Problem),即寻找从一个城市到另一个城市的最短路线,答案非常容易验证,不过,如果P≠NP,就没有计算机程序可以迅速给出这个答案。
迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可,但一周后公布的论文终稿还将接受严格的审查。(记者陈丹)
本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
据报道,在美国旧金山的一次诉讼中,英国科技公司Autonomy联合创始人Mike Lynch被惠普指控在该公司以110亿美元出售给惠普涉及会计欺诈。
关键字:
惠普
Autonomy
收购
北京2024年5月13日 /美通社/ -- 5月11日,软通动力在鲲鹏昇腾开发者大会2024期间举办"软硬全栈,加速智能化赋能"分论坛。业界专家学者和优秀企业代表齐聚一堂,共同交流分享鲲鹏昇腾生态的创...
关键字:
智能化
全栈
PEN
计算机
卡西欧计算机株式会社宣布推出与冲浪者基金会合作设计的G-SHOCK系列新款防震手表G-5600SRF,旨在保护海洋。这款手表的表圈和表带由回收树脂废料制成,展现独特设计。配备Tough Solar太阳能充电系统,强调环保...
关键字:
手表
SHOCK
SOLAR
计算机
随着信息技术的迅猛发展和大数据时代的到来,机器学习成为了人工智能领域中的核心技术之一。机器学习是通过模拟人类学习行为,使计算机系统能够从数据中自动发现规律、提取特征并进行预测和决策的过程。它在诸多领域取得了广泛的应用,包...
关键字:
计算机
人工智能
机器学习
随着大数据时代的到来,数据处理成为了一项至关重要的任务。传统的数据处理方法往往面临着效率低下、准确性不高等问题,而机器学习技术的兴起为数据处理带来了全新的解决方案。本文将深入探讨机器学习在数据处理中的应用,并分析其优势和...
关键字:
数据处理
计算机
机器学习
机器学习是人工智能领域的一个重要分支,它使用各种算法来使计算机系统能够从数据中学习和改进,而无需进行明确的编程。在机器学习的广阔领域中,有多种算法被广泛应用,每种算法都有其独特的适用场景和优势。本文将详细介绍机器学习中的...
关键字:
机器学习
人工智能
计算机
随着信息技术的飞速发展,机器学习(Machine Learning)作为人工智能领域的重要分支,正在逐步改变我们生活的方方面面。那么,什么叫做机器学习呢?简单来说,机器学习是一门研究如何让计算机从数据中自动获取知识和技能...
关键字:
机器学习
人工智能
计算机
随着信息技术的飞速发展,数据已经成为现代社会的重要资源。数据挖掘和机器学习作为处理和分析数据的两大关键技术,在多个领域得到了广泛应用。尽管它们在某些方面存在重叠,但数据挖掘和机器学习在定义、目标、方法以及应用场景等方面存...
关键字:
数据挖掘
机器学习
计算机
一直以来,因数都是大家的关注焦点之一。因此针对大家的兴趣点所在,小编将为大家带来因数的相关介绍,详细内容请看下文。
关键字:
因数
功率因数
计算机的历史可以追溯到公元前的古代算盘和查尔斯·巴贝奇的“分析机”构想。然而,现代意义上的计算机起源于二战时期对复杂军事计算需求的响应。1941年,美国宾夕法尼亚大学开发出了ENIAC(Electronic Numeri...
关键字:
计算机
云服务
自二十世纪以来,计算机技术经历了从机械计算装置到如今高度智能化、微型化的巨大飞跃,成为人类科技进步的重要推动力。电脑的发展史是一段充满创新与突破的历史,以下将按照时间顺序概述这一发展历程。
关键字:
电脑
计算机
计算机网络是当今信息化社会中不可或缺的基础设施,它将世界各地的计算机系统及其附属设备紧密联系在一起,实现了信息的高速传输与共享资源的有效利用。计算机网络的定义可以归纳为:计算机网络是一系列分布在不同地理位置、具备独立功能...
关键字:
计算机
信息交互
随着科技的不断进步,人工智能(AI)已成为当今世界的热门话题。它以其强大的计算能力和深度学习能力,在多个领域展现出巨大的应用潜力。本文将对人工智能技术进行详细的探究,包括其定义、发展历程、主要技术、应用领域以及面临的挑战...
关键字:
人工智能
深度学习
计算机
4月1日消息,戴尔在中国的PC销量持续下滑(份额已被华为超越),这迫使他们不得不采取更多的裁员措施。
关键字:
戴尔
PC
计算机
业内消息,俄乌冲突之后,美国科技企业基本都退出了俄罗斯、白俄罗斯市场,但现在,不少企业连仅存的服务支持都切断了。近日惠普正式关闭了俄罗斯官网,俄罗斯用户打开惠普官网会被跳转到哈萨克斯坦官网,因为两国语言相通。
关键字:
惠普
俄罗斯
人工智能(Artificial Intelligence,AI)是一门涉及计算机、工程、数学、哲学和认知科学等多个领域的交叉学科,旨在构建智能化计算机系统,使之能够自主感知、理解、学习和决策。
关键字:
机器学习
人工智能
计算机
随着科技的飞速发展,计算机已经成为我们日常生活和工作中不可或缺的工具。然而,有时我们可能会遇到一些棘手的问题,如忘记BIOS密码。BIOS(基本输入输出系统)是计算机启动过程中的重要部分,它负责初始化硬件并加载操作系统。...
关键字:
bios密码
计算机
今天,小编将在这篇文章中为大家带来防火墙的有关报道,通过阅读这篇文章,大家可以对它具备清晰的认识,主要内容如下。
关键字:
防火墙
计算机
随着人工智能(AI)技术的迅速发展,人们对于通用人工智能(AGI,即Artificial General Intelligence)的期待也日益高涨。通用人工智能指的是具备像人类一样全面智能的计算机系统,能够执行各种复杂...
关键字:
人工智能
计算机
数据
在数字电路和计算机体系结构中,定序器(Sequencer)是一个至关重要的组件。它负责协调和控制各个功能单元的操作顺序,确保数据在正确的时间被传输和处理。尽管定序器在许多现代电子系统中都扮演着关键角色,但对于非专业人士来...
关键字:
数字电路
计算机
定序器