NP困難問題（NP-hard problem）是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。
基本介紹
- 中文名：NP困難問題
- 外文名：NP-hard problem
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
NP困難問題
相關詞條
- NP困難問題
NP困難問題（NP-hard problem）是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義給定一個問題A，如果任何NP問題均在多項式時間多一歸約、對數空間多一歸約或多項式時間圖靈歸約下歸約於A，那...
- NP(未解難題)
NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。釋義 P/NP問題是在理論信息學中計算複雜度理論領域裡至今沒有解決的問題，它被“克雷數學研究所”（Clay Mathematics Institute, 簡稱CMI）在千禧年大獎...
- NP完全問題
NP完全問題(NP-C問題)，是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。詳細信息 P類問題 ...
- NP難問題
NP難問題 NP難問題（NP-hard problem）是2016年全國科學技術名詞審定委員會公布的管理科學技術名詞。定義 需要超多項式時間才能求解的問題。出處 《管理科學技術名詞》第一版
- P/NP問題
若任何一個NP完全的問題在P內，則可以推出P = NP。不幸的是，很多重要的問題被證明為NP完全，但沒有一個有已知快速的算法。處理 上面所有的討論假設了P表示“容易”而“不在P中”表示“困難”。這是一個在複雜度理論中常見而且有...
- 旅行商問題
旅行推銷員問題（英語：Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。它是組合最佳化中的一個NP難問題，在運籌學和理論計算機科學中非常重要。
- NP複雜度
NP完全問題（NP-complete problems）如果一個問題既是NP困難問題又是NP問題，我們稱之為NP完全問題。例子 比如說，我們不知道81,785,036,517是否為素數，但是要確定277,877是否為81,785,036,517因數，我們可以直接拿去除。針對277,877...
- 圖上若干基本NP難問題的算法研究
《圖上若干基本NP難問題的算法研究》是依託電子科技大學,由肖鳴宇擔任醒目負責人的青年科學基金項目。項目摘要 本項目主要從參數算法、精確算法和近似算法的角度來研究計算機中一些基本的圖問題，其中包括被稱之為六個基本NP難問題的獨立集...
- 一類NP-難解問題的智慧型算法
《一類NP-難解問題的智慧型算法》是依託山東大學，由馬紹漢擔任項目負責人的面上項目。中文摘要 本課題研究的內容是一類NP—難解問題的智慧型算法，本研究工作在理論上的創新點是；（1）對博弈樹搜尋問題的SSS算法進行改進，並提出高效分散式...
- P類問題
P/NP問題是在理論信息學中計算複雜度理論領域裡未被解決的問題，也是克雷數學研究所七個千禧年大獎難題之一。P/NP問題中包含了複雜度類P與NP的關係。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相對獨立地提出了下面的問題，...
- NP(非確定性多項式時間)
一個便於理解的詮釋是，NP 問題是一類可在多項式時間內驗證你給出的答案是否正確的問題。NP 相關問題 NP 相關的問題中一個重要的概念是 NP-complete 問題。如果對於某一個 NP 問題 L, NP 中所有的問題 A 都可以在多項式時間內多一...
- 計算機數學 : 計算複雜性理論與NPC,NP難問題的求解
《計算機數學 : 計算複雜性理論與NPC,NP難問題的求解》是2001年1月科學出版社出版的圖書，作者是陳志平，徐宗本。內容簡介 本書共分十六章，主要介紹了計算複雜性理論的基本內容與各種NPC問題、NP難問題等複雜問題的計算機求解方法。圖書...
- NP-hard
NP-hard，指所有NP問題都能在多項式時間複雜度內歸約到的問題。基本介紹 其中，NP是指非確定性多項式（non-deterministic polynomial，縮寫NP）。所謂的非確定性是指，可用一定數量的運算去解決多項式時間內可解決的問題。例如，著名的推銷...
- 集合覆蓋問題
集合覆蓋問題的決定性問題為，給定 和一個整數k，求是否存在一個大小不超過k的覆蓋。集合覆蓋的最佳化問題為給定 ，求使用最少的集合的一個覆蓋。決定性問題的集合覆蓋是NP完全問題，最佳化問題的集合覆蓋是NP困難問題。此外，問題可以...
- 線性規劃問題
相對於即使在最壞情況下也能有效率地解出的線性規劃問題，整數規劃問題的最壞情況是不確定的，在某些實際情況中（有約束變數的那些）為NP困難問題。0-1整數規劃是整數規劃的特殊情況，所有的變數都要是0或1（而非任意整數）。這類...
- 近世計算理論導引——NP難度問題的背景、前景及其求解算法研究_百度...
近世計算理論導引——NP難度問題的背景、前景及其求解算法研究 數學機械化叢書 -5 黃文奇,許如初 著 2004年6月出版 定價:20.00 語種:中文 標準書號:7-03-012617-3 裝幀:精裝 版本:第一版 開本:B5 責任編輯:呂虹 字數:105千字 ...
- NP難解問題的近似算法
NP難解問題的近似算法 《NP難解問題的近似算法》是1998年世界圖書出版公司出版的圖書，作者是Dorit S.Hochbaum。內容介紹 Approximation al 作品目錄 Introduction Do
- 大規模最大割問題的連續化近似算法及推廣
《大規模最大割問題的連續化近似算法及推廣》是依託西安交通大學，由徐成賢擔任項目負責人的面上項目。中文摘要 最大割問題是一類基本的有廣泛套用的組合最佳化問題,它是一類NP-困難問題, 典型的求解方法是近似算法.對大規模最大割問題目前...
- NP完全問題求解複雜性研究
《NP完全問題求解複雜性研究》是依託中國人民解放軍國防科技大學，由姜新文擔任項目負責人的面上項目。中文摘要 NP=?P的問題是計算機科學和數學中的著名問題。美國克雷數學研究院將其列為新千年7大急需解決的困難問題之首。Science雜誌2005...
- NP完全性
計算複雜性理論中的一個重要概念，它表征某些問題的固有複雜度。一旦確定一類問題具有NP完全性時，就可知道這類問題實際上是具有相當複雜程度的困難問題。簡介 探討各種各樣問題是否具有NP完全性，研究NP完全問題的處理方法，這對許多實際...
- NP-Complete(計算複雜性中的NP完全)
它是一個NP問題，且 其他屬於NP的問題都可歸約成它。可歸約在此意指對每個問題L，總有一個多項式時間多對一變換，即一個決定性的算法可以將實例l∈L轉化成實例c∈C，並讓c回答Yes若且唯若此答案對l也是Yes。為了證明某個NP問題...
- 選址問題
對於空間 P-中位問題，也就是更一般的Weber 問題，Rosing提出了最優解法。Garey 和 Johnson證明了 P-中位問題是 NP-困難問題。Francis、Francis 和 Cabot、Chen以及 Chen 和 Handler研究了基於歐氏距離的 P-中位問題。（2）P-中心...
- 非確定性多項式難題
NPC(NP Complete，NP完全)問題 計算機科學家將NP問題中最困難的稱為NPC問題。NPC問題有一個令人驚訝的性質，即如果一個NPC問題存在多項式時間算法，那么所有NP問題都可以在多項式時間內求解，即P=NP成立。這是因為每一個NPC問題都可以在...
- 世界七大數學難題
NP完全問題 例：在一個周六的晚上，你參加了一個盛大的晚會。由於感到局促不安，你想知道這一大廳中是否有你已經認識的人。宴會的主人向你提議說，你一定認識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘，你就能向那裡掃視，並且發現...
- 裝配型排序理論- - 計算複雜性、近似算法和隨機算法
排序論是運籌學和組合最最佳化領域極為活躍的研究分支,而裝配型排序則包含了豐富的經典及新興排序模型.排序問題的計算複雜性研究,即確定一個排序問題是多項式時間可解還是NP-困難的,向來是排序論的主要研究方向.NP-困難問題的近似算法和隨機...
- 多代理多工序排序理論:計算複雜性與可近似性
例如：多目標排序、多機作業排序、多階段供應鏈排序、分批排序等.排序問題的計算複雜性研究,即確定一個排序問題是多項式時間可解還是NP-困難的,向來是排序論的主要研究方向.NP-困難問題的近似算法和線上算法則是近年來國際上流行的研究...
- Menger數
“確定圖的Menger數”問題是NP-困難的。基本介紹 設x，y為圖G的兩個節點，若G的一個節點子集S，x，y∈S，使得在圖G-S中不再有連x與y的路，則稱S為G的一個(x，y)分離子。若S是G上的一個(x，y)分離子，但它的任何一...
