NP问题
NP问题 - 搜索结果 - 维基百科，自由的百科全书
在维基百科上已有名为“NP问题”的页面
polynomial，缩写：NP）是计算理论中最重要的集合之一，它包含P和NP-complete。 P問題是指在多项式时间内，可以找出解的決定性問題(decision problem)，而NP問題則包含可在多项式时间內驗證其解是否正確，但不保證能在多項式時間內能找出解的決定性問題。NP包含P和NP-complete问题,…- P/NP问题是理论计算机科学中计算复杂度理论领域至今未解决的问题，是克雷数学研究所七題千禧年大奖难题之一。P/NP问题包括复杂度类P与NP的关系。1971年由史提芬·古克（Stephen A. Cook）和列昂尼德·列文（英语：Leonid Levin）分別提出。…
- NP完全或NP完备 （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP完備問題…
- 因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。 NP (複雜度) NP完全 P/NP问题 歸約 Michael R. Garey; David…
- 藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P = NP這些問題。 卡普的21個問題列表如下。下列问题加上了缩进排版，以表示出這些問題歸約的方向。例如，精确覆盖问题可以歸約到背包問題（Knapsack），因此背包問題是NP-完全問題。 布爾可滿足性問題…
- {X}}} 問題，因此我們可以為所有NP問題建造一個可在多項式時間判定其補性質的非確定型圖靈機，意即NP是反NP的子集。因此NP問題的補集合是一個反NP問題的補集合的子集，意即反NP是NP的子集。由於我們已知NP是反NP的子集，因此表示這兩個集合是一樣的，這證明了沒有反NP完全問題可在NP類之中的性質是對稱的（Symmetrical）。…
- 图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图 G = ( V , E ) {\displaystyle G=(V,E)} ，其中 V {\displaystyle V} 为顶点集合， E {\displaystyle…
- 可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布尔可滿足性問題（Boolean satisfiability problem；SAT ）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多的領域皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。…
problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。 哈密顿环问题与哈密顿路径问题之间有着很简单的关系： 给定图G{\displaystyle G} ,通过加入新顶点v{\displaystyle v}…
旅行商问题（英語：Travelling salesman problem，縮寫：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每對城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。” TSP是旅行购买者问题（英语：travelling…- 在計算複雜度理論內，NP-易（或称“NP-容易”，NP-easy）這個複雜度類是使用帶有在NP裡面某個決定性問題神諭的圖靈機，能在多項式時間內解決掉的功能性問題。 換句話說，一個問題X屬於NP-易，若且唯若存在某個在NP裡面的問題Y，令X可以於多項式時間內圖靈歸約（polynomial-time Turing…
背包问题（英語：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品…- NP完备的定义，我们知道对这其中任何一个问题的多项式算法都将给出所有NP问题，也包括所有NP完备问题的多项式算法。然而尽管实际问题中遇到很多NP完备的问题，而且有很多问题在不同领域有着相当的重要性而被大量研究，至今，仍没有对NP完备问题的多项式算法，这是一些理论计算机科学家认为NP≠P的理由之一。…
- 这个文章是在计算机科学中的有待解决的问题的列表。当该领域专家认为某些问题未解决，或当该领域中的几位专家不同意有关解决问题的办法时，这些计算机科学中的问题就被认为是未解决的。 P = NP问题。这是七个千禧年大奖难题之一 NC (複雜度) NP = co-NP问题 P = BPP问题 P = PSPACE问题 BQP和NP之间的关系是什么？…
- 此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美國國家標準和技術研究院（NIST）的 Alan Goldman 首先將此問題命名为中国邮递员问题。…
- 三维匹配问题（3DM）是六个经典NP完全问题之一，是经典的“婚姻问题”的推广，“婚姻问题”的提法是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？ 在三维匹配问题中，可以用集合 W {\displaystyle…
- 在一个全集X中若干子集的集合为S，精确覆盖是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。 在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题，也是卡普的二十一个NP-完全问题之一。 满足以下条件的集合为一个精确覆盖： S*中任意两个集合没有交集，即X中的元素在S*中出现最多一次…
- 5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。 一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使得子集中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。 用动态规划的方法，能够以伪多项式时间解决子集合加总问题。我们假定输入序列为： x1…
- 集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 给定全集U{\displaystyle {\mathcal {U}}}，以及一个包含n{\displaystyle…
- Np可以指： 镎：一种化学元素。 奈培（Neper）：物理學單位。 新元古代（Neoproterozoic）。 沒有關係 / 沒有問題 (No problems) NP可以指： NP (复杂度)：非定常多項式，算法的复杂度。 電話號碼可攜服務（Number Portability）。 日本海事協會標準：日本海事協會。…
- NP-hard问题，即目前为止无最优解问题
- 𝛿 和角频率 𝜔 的 SI 一贯单位是负一次方秒（s⁻¹）。𝛿𝑡 和 𝜔𝑡 的单位分别用专门名称奈培（Np）和弧度 (rad) 时 𝛿 和 𝜔 的单位分别为奈培每秒（Np/s）和弧度每秒 (rad/s) 。当奈培用作对数量的单位，弧度用作平面角和圆函数的相位的单位时，可把它们看作是“无量纲量”的单位
- 取期望与仿射变换可交换运算顺序：E(aX + b) = aEX + b 如果随机变量X服从两点分布，那么EX = p。 如果X ~ B(n, p)，那么EX = np。 如果离散型随机变量 ξ {\displaystyle \xi } 的所有可能取值是 x 1 , x 2 , ⋯ , x n , ⋯ {\displaystyle
- NP問題就是理論電腦科學中的著名問題。 數量的研究起於數，一開始為熟悉的自然數及整數與被描述在算術內的自然數及整數的算術運算。整數更深的性質於數論中有詳細的研究，此一理論包括了如費馬最後定理等著名的結果。數論還包括兩個被廣為探討的未解問題：孿生質數猜想及哥德巴赫猜想。