基本介紹
- 中文名:非確定性多項式難題
- 外文名:Nondeterministic Polynomially problem
- 簡稱:NP問題
- 舉例:完全子圖問題、旅行商問題等
- 相關概念:P問題,NPC問題等
NP(Nondeterministic Polynomially,非確定性多項式)類問題是指一個複雜問題不能確定是否在多項式時間內找到答案,但是可以在多項式時間內驗證答案是否正確。NP類問題數量...
簡介NP,即非確定性多項式 Non-deterministic polynomial的縮寫。所謂非確定性,就是指可以用一定數量的運算去解決多項式時間內可解決的問題。NP 問題通俗來說是其解的...
NP完全問題(NP-C問題),是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題,即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P?,問題...
NP的英文全稱是Non-deterministic Polynomial的問題,即多項式複雜程度的非確定性問題。...
NP問題是指存在多項式算法能夠驗證的非決定性問題,而其中NP完全問題又是最有可能不是P問題的問題類型。所有的NP問題都可以用多項式時間歸約到他們中的一個。所以...
人們發現,所有的完全多項式非確定性問題,都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案,都可以在多項式時間內計算,人們於是就猜想,是否...
有限時間內完成計算;NP指非確定性多項式時間(nondeterministic polynomial),一個複雜問題不能確定在多項式時間內解決,假如NP問題能找到算法使其在多項式時間內解決,也...
NP是目前為止還未找到多項式解法的問題。對於這些問題,我們目前也不知道是否存在多項式的解法。所以叫非確定多項式問題。NP代表“Non-deterministic(非確定性)Polynomial...
所謂非確定性是指在理論計算機科學中,針對各種計算機器模型(自動機),在每一時刻,根據當時的狀態和輸入,若機器有多個動作可供選擇時,則稱機器為非確定性的;相反,...
UNIQUE-SAT是確定公式是否只有一個賦值的問題。對於美國來說,它是完整的,描述了由非確定性多項式時間圖靈機解決的問題的複雜性類,當只有一個非確定性接受路徑時它...
P-NP I}}題(P-NP problem)亦稱P=? NP問題,計算複雜性理論以及計算機理論中最重要的一個未解決問題。它問在多項式時間界下,確定型圖機接受的語言類是與非...
可以在多項式時間驗證答案的決定性問題稱為NP。而NP也是可以在非確定型圖靈機以多項式時間解決的問題(NP兩字為Non-deterministicPolynomial的縮寫)。多項式時間在決定型...
表達的時間內解決的問題;類NP由所有可以在多項式時間內驗證它的解是否正確的決定問題組成,或者等效的說,那些可以在非確定型圖靈機上在多項式時間內找出解的問題的...
的時間內解決的問題;類NP由所有其肯定解可以在給定正確信息的多項式時間內驗證的決定問題組成,或者等效的說,那些解可以在非確定圖靈機上在多項式時間內找出的問題的...
分支問題NP完全問題 編輯 NP完全問題,又叫NP-C問題,是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題,即多項式複雜程度的非確定性問題。...
所謂的非確定性 作用 解決問題 目錄 1 NP-hard 2 形式化定義 NP-hardNP-hard 編輯 其中,NP是指非確定性多項式(non-deterministic polynomial,縮寫NP)。所謂的...
一個計算問題的時間複雜性與算法有關非確定性多項式複雜性(NP-問題)懸賞1OO萬美金的難題(P=NP?)第二篇 面對複雜15.複雜之源——非線性是導致複雜性的根源...
非定常多項式(英語:non-deterministic polynomial,縮寫:NP)時間複雜性類,或稱非確定性多項式時間複雜性類,包含了可以在多項式時間內,對一個判定性算法問題的實例,一...
P:包含可以使用確定型圖靈機在多項式時間內解決的決定性問題。 NP:包含可以使用非確定型圖靈機在多項式時間內解決的決定性問題。 ZPP:包含可以使用機率圖靈機在...
P的擴大集合是NP,此複雜度類別是一個可在多項式時間以非確定型圖靈機決定答案的問題的集合。因此我們可知道P是NP的子集,且雖然未證明,但大部分專家相信P是NP的...
圖靈機可分為確定型和非確定型。確定型圖靈機在多項式時間內可解決的全部問題類記作 P。非確定型圖靈機在多項式時間內可解決的全部問題類,記作NP。由於確定型...
第10章 NP完全問題10.1 非確定型圖靈機問題10.2 P類和NP類10.3 語言和問題10.4 可滿足性問題的NP完全性lO.5 其他NP完全問題10.6 多項式空間界問題...
Cook-Levin定理,也稱為Cook定理,表明布爾可滿足性問題是NP完全的。 也就是說,NP中的任何問題都可以通過確定性圖靈機在多項式時間內減少到確定布爾公式是否可滿足的...
在全體判定問題中,NL類包含了那些可以用非確定型圖靈機在對數空間內解決的問題...由於這種圖靈機的格局數目只有多項式級別,因此NL和L都是P的子集。正式地說,一...