NP (複雜度)
非確定性圖靈機在多項式時間內可解決的決策問題的計算複雜度類別 / 維基百科,自由的 encyclopedia
親愛的 Wikiwand AI, 讓我們通過簡單地回答這些關鍵問題來保持簡短:
你能列出最重要的事實和統計數據嗎 NP (複雜度)?
為 10 歲的孩子總結這篇文章
顯示所有問題
非決定性多项式集合(英語:non-deterministic polynomial,缩写:NP)是计算理论中最重要的集合之一,它包含P和NP-complete。
P問題是指在多项式时间内,可以找出解的決定性問題(decision problem),而NP問題則包含可在多项式时间內驗證其解是否正確,但不保證能在多項式時間內能找出解的決定性問題。NP包含P和NP-complete问题, 因此NP集合中有簡單的問題和不容易快速得到解的難題。
“NP是否等於P”是计算机科学中知名的難題。