P/NP问题，一个困扰理论信息学和计算复杂度理论领域的未解难题，由克雷数学研究所收录在千禧年大奖难题中。问题核心在于理解复杂度类P与NP之间的关系。P类包含那些在多项式时间内由确定型图灵机解决的问题，而NP则包含那些其肯定解可以在给定正确信息下在多项式时间内验证的问题，即非确定图灵机可以在多项式时间内找出解的问题。
关于P是否等于NP，学术界存在分歧。2002年的研究者调查中，大多数人相信答案是否定的。P=NP问题的解决将对计算理论产生深远影响，例如，如果旅行商问题被证明在P内，将直接得出P=NP的结论。然而，至今尚未找到NP完全问题的多项式时间算法，这被认为是P≠NP的一个关键证据。
P和NP之间的关系被直观地解释为，验证答案是否正确相对容易，但找到答案本身是否同样快速则是问题所在。例如，判断一个数是否为合数，虽然验证很快，但找出因子可能需要大量时间。这使得NP完全问题成为理解这两类关系的关键，它们是NP中最难但可能不属于P的问题，如旅行商问题。
尽管存在争议，学术界普遍认为P≠NP，因为经典计算模型（如图灵机）的局限性以及已知的多项式时间算法在NP完全问题上的缺失。一些理论学家认为，我们可能过于偏重于P≠NP，而忽视了证明其相反的可能。同时，关于证明难度的数学定理，如Razborov和Rudich的结果，显示了证明P=NP的困难性。
尽管如此，仍有人在探索P=NP的可能性，比如通过寻找可能存在的魔法机器，它可以在瞬间解决特定问题。然而，这样的机器若存在，可能会导致已知证明方法的失效。P和NP问题的解决仍然是理论计算机科学领域的一大挑战，其答案尚未明确，但已有的研究和理论成果为未来的探索提供了线索。
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。 P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?）。