NP（Non-deterministic Polynomial）是计算复杂度理论的核心概念，探讨P与NP是否相等，被克雷数学研究所列为千禧年大奖难题之一 。
P类问题指可由确定型图灵机在多项式时间内解决的问题，NP类问题则由能在多项式时间内验证解的问题组成。NP完全问题是NP类中最难的问题，若任一NP完全问题属于P则P=NP成立 。2002年调查显示，61位研究者认为P≠NP 。
该问题由史提芬·古克和Leonid Levin于1971年提出 ，克雷数学研究所为其设立百万美元奖金 。
想要了解更多“NP（未解难题）”的信息，请点击：NP（未解难题）百科
