P/NP问题是一个在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相对独立地提出了下面的问题，即复杂度类P和NP是否是等价的（P=NP?）。

不过，据寻小山问答小编了解，2010年8月7日，来自惠普实验室的科学家迪奥拉里卡（Vinay Deolalikar）声称已经解决了“P/NP问题” ，并公开了证明文件。迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可，但随后公布的论文终稿还将接受严格的审查才能获得大众认可。