网站首页  情感咨询  情感美文  情感百科  情感生活  学习充电  旧版美文

请输入您要查询的词汇：

　

词汇 NP problem
分类 英语词汇 英语翻译词典
释义

NP problem

中文百科

P/NP问题 P versus NP problem

（重定向自NP problem）
假设P ≠ NP的复杂度类的图解。如P = NP则三个类相同。
Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos, fue determinada por Richard E. Ladner.[1]

P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?）。

英语百科

P versus NP problem P/NP问题

（重定向自NP problem）
Diagram of complexity classes provided that P ≠ NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by Ladner's theorem.[1]
Euler diagram for P, NP, NP-complete, and NP-hard set of problems
The graph shows time (average of 100 instances in ms using a 933 MHz Pentium III) vs.problem size for knapsack problems for a state-of-the-art specialized algorithm. Quadratic fit suggests that empirical algorithmic complexity for instances with 50–10,000 variables is O((log(n))2).[15]
Représentation visuelle des deux configurations possibles.

The P versus NP problem is a major unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.

It was essentially first mentioned in a 1956 letter written by Kurt Gödel to John von Neumann. Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time. The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.
随便看

　

依恋情感网英汉例句词典收录3870147条英语例句词条，基本涵盖了全部常用英语单词的释义及例句，是英语学习的有利工具。

　

Copyright © 2004-2024 Yiyi18.com All Rights Reserved
京ICP备2021023879号 更新时间：2025/8/6 2:54:11