NP難問題（NP-hard problem）是2016年全國科學技術名詞審定委員會公布的管理科學技術名詞。
基本介紹
- 中文名：NP難問題
- 外文名：NP-hard problem
- 所屬學科：管理科學技術
- 公布時間：2016年
定義,出處,
NP難問題
相關詞條
- NP完全問題
NP完全問題(NP-C問題)，是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。詳細信息 P類問題 ...
- NP難問題
NP難問題 NP難問題（NP-hard problem）是2016年全國科學技術名詞審定委員會公布的管理科學技術名詞。定義 需要超多項式時間才能求解的問題。出處 《管理科學技術名詞》第一版
- NP完全性
NP完全問題就是NP中最難問題的一種形式化。多項式時間歸約假定給了兩個問題類q和q0,如果存在一個確定型圖靈機Mq和一個多項式P,對於q中任意一個實例x,Mq都能在P(n)時間內計算出q0中一個實例y(其中n是實例x的編碼長度)，使得x...
- 旅行商問題
旅行推銷員問題（英語：Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。它是組合最佳化中的一個NP難問題，在運籌學和理論計算機科學中非常重要。
- 計算機和難解性 : NP完全性理論導引
第六章集中研究NP難問題的近似算法．第七章概述了大量計算複雜性中有關的理論課題．附錄A收集了範圍廣泛、內容豐富的NP完全問題和NP難的問題．附錄B補充了NP問題的一些最新進展，既有理論方面的，又有關於具體問題的．...
- 二部圖上NP完全問題的研究
《二部圖上NP完全問題的研究》是依託北京大學，由劉田擔任負責人的面上項目。項目摘要 二部圖是重要的圖類，不僅可用來為實際問題建模，還可獲得在一般圖上難以獲得的結論，其內部包含豐富的結構，可定義各種特殊的二部圖，如凸二部圖...
- 選址問題
Garey 和 Johnson證明了 P-中位問題是 NP-困難問題。Francis、Francis 和 Cabot、Chen以及 Chen 和 Handler研究了基於歐氏距離的 P-中位問題。（2）P-中心問題（p-center problems）P-中心問題也叫 minmax 問題，是探討如何在網路中...
- 難解問題的固定參數近似算法研究
《難解問題的固定參數近似算法研究》是依託湖南師範大學，由劉運龍擔任項目負責人的面上項目。項目摘要 固定參數近似算法採用參數計算方法尋求問題的近似解，是實際處理難解問題的一種新的有效手段。本項目深入地研究一系列NP-難解問題的...
- 背包問題
背包問題(Knapsack problem)是一種組合最佳化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包...
- NP最優問題的機率近似算法設計和平均複雜性設計
對於NP最佳化問題給出了一種新的歸約和邏輯定義，使得對數近似度的NP最佳化總是從常數近似度及多項式近似度的NP最佳化問題中分離出來。對集合論和圖論中的某些經典問題給出了新的隨機和褪隨機算法。從計算複雜性的角度對零知識證明進行了較為...
- P類問題
P/NP問題是在理論信息學中計算複雜度理論領域裡未被解決的問題，也是克雷數學研究所七個千禧年大獎難題之一。P/NP問題中包含了複雜度類P與NP的關係。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相對獨立地提出了下面的問題，...
- 分支問題
NP完全問題 NP完全問題，又叫NP-C問題，是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。
- 基於NP完全類問題的抗量子計算密碼基礎理論研究
《基於NP完全類問題的抗量子計算密碼基礎理論研究》是依託北京大學，由馮榮權擔任負責人的聯合基金項目。項目摘要 量子計算機的出現必然對我國現有密碼系統帶來強烈的衝擊，因此本課題擬對抗量子密碼體制展開研究，探索具有自主智慧財產權的抗量子...
- NP完全集
NP問題密切相關，這正是它的魅力所在.第一個NP完全集的例子是庫克(Cook , S. A. >於1971年給出的可滿足性問題的集SAT.卡普(Karp , R. M.)於1972年給出了NP完全性這一術語的明確表述及其嚴格的形式定義，並給出了21個NP完全...
- 信息科學中圖與超圖劃分問題的隨機近似算法研究
由於大部分圖與超圖劃分問題都是NP困難的甚至難近似的, 一般都具有較為抽象的組合結構，所以很難僅從結構分析的角度得到解決。本課題選擇幾類在信息科學中有重要套用價值的圖與超圖劃分問題，即有容量限制的聚類瓶頸劃分、圖的均衡存儲...
- 非確定性多項式難題
這就是所謂的“NP問題”。目前P與NP是否等價是一個既沒有證實也沒有證偽的問題。但是大部分科學家猜想：找一個問題的解很困難，但驗證一個解很容易(證比解易)，用公式表示就是P≠NP。問題較難求解(P)但容易驗證(NP)，這與我們...
- 世界七大數學難題
1.NP完全問題 例：在一個周六的晚上，你參加了一個盛大的晚會。由於感到局促不安，你想知道這一大廳中是否有你已經認識的人。宴會的主人向你提議說，你一定認識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘，你就能向那裡掃視，並且...
- 曼哈頓網路
郭澤宇提出解決最小曼哈頓網路的算法複雜性NP難問題是不太現實的，但改善現有解決方案的效率或提高近似度是可行的研究方向，郭澤宇的結果是2-近似O(n2)時間複雜度。能否將效率提高到O(nlogn)，與3-近似方法相同？或提出1.5-近似的新...
- 運籌學(原書第2版)
14.1 問題、實例和求解的難度743 14.2 衡量算法複雜性及問題的難度745 14.3 可解問題的多項式時間驗證標準748 14.4 多項式可解和非確定多項式可解749 14.5 多項式時間歸約和NP難問題753 14.6 P問題和NP問題755 14.7 ...
- 計算複雜性理論(理論計算機科學分支學科)
而在計算複雜性中，Khuller和Vazirani在1990年代證明了在P≠NP的假設下，平面圖4-著色問題的判定型問題是在P中的，而尋找其字典序第一的著色是NP難的。所以在可計算性理論中，只關注判定型問題是合理的。在計算複雜性理論中，雖然...
- 約束最佳化法
（2） 很多難於處理的問題（np難，或者np完全等）是包含約束條件的。這使得約束最佳化問題在理論上非常具有挑戰性。約束最佳化問題的具體形式如下：min f(x)滿足約束條件 g(x)h(x)=0 其中x是解向量，g(x)是不等式約束，h(x)是...
- 罰函式法
在進化計算中，研究者選擇外部罰函式法的原因主要是該方法不需要提供初始可行解。需要提供初始可行解則是內部罰函式法的主要缺點。由於進化算法套用到實際問題中可能存在搜尋可行解就是NP難問題，因此這個缺點是非常致命的。外部罰函式法一般...
- 數學規劃與組合最佳化
第八章 組合最佳化問題和計算複雜性 8.1 組合最佳化問題與算法 8.2 算法時間複雜性 8.3 NP類 8.4 NP—完全問題與NP—難問題 8.5 處理NP—難問題 第九章 背包問題 9.1 問題的措述 9.2 分枝定界法 9.3 近似算法 9.4 0-...
- 數學難題
一、P（多項式時間）問題對NP（nondeterministic polynomial time，非確定多項式時間問題）在一個周六的晚上，你參加了一個盛大的晚會。由於感到局促不安，你想知道這一大廳中是否有你已經認識的人。你的主人向你提議說，你一定認識那位正在...
