以短证书定义问题类
NP是计算复杂度理论中的语言类，英文名称是nondeterministic polynomial time。用证书定义时，存在一个确定性核验器V和多项式p，使输入x属于语言，当且仅当存在长度不超过p(|x|)的字符串c令V(x,c)接受，而且核验时间受输入长度的多项式限制。
两个量词条件都重要：肯定实例至少有一份能通过的证书；否定实例则不能靠任何允许长度的证书蒙混过关。定义不要求每份证书都正确，也不要求能够快速找到正确证书。证书长度必须有界，否则“验证很容易”可能掩盖读取巨大候选答案的成本。
参考：[1]
团与可满足性
对于团问题，输入是一张图和整数k，证书列出k个顶点。核验器检查顶点互不重复，并逐对确认它们之间都有边。这些操作的次数是输入规模的多项式；若图中没有这样的团，则不论交来哪组顶点，总会在某项检查上失败。
SAT的证书是一组布尔变量赋值。将它代入公式并计算结果，就可验证公式可满足。比如x∨y的赋值x=1、y=0能通过；赋值0、0不能通过，却不说明该公式不可满足。一个失败候选只否定自身，不能替代对所有候选的排除。
与非确定性机器的等价
非确定性图灵机可以先作一系列选择，写出多项式长度的候选证书，再确定性地核验。只要有一条分支接受，就接受输入；所有分支均须在多项式步数内结束。反过来，一条接受分支的选择序列可作为证书，由确定性机器按序重放。这连接了证书定义与机器定义。
这里没有假设现实计算机能免费同时运行所有分支，也没有给选择赋予成功概率。若简单随机抽取证书，正确证书可能只占极小比例，因而不能从NP成员资格直接推出一个高成功率的随机多项式时间算法。
P、NP完全与否定证书
确定性多项式时间类P包含于NP，因为核验器可以忽略证书，直接运行已有算法。因此NP中的N并不是“非”的意思，不能把NP理解为所有非多项式问题。NP完全问题是NP中在多项式归约下足以表示整个类的一部分，并非NP的同义词。
NP定义只要求肯定答案的短证书。否定答案是否也有同类证书，是与coNP有关的另外问题，不能通过交换非确定性分支的接受、拒绝直接解决。P是否等于NP仍未确定：它询问所有这种可高效核验的问题是否也能高效判定，而不是询问某个指定算法能否进一步加速。