NP问题是给出解决方案的问题,您可以在多项式时间内验证解决方案.例如,如果您有一个大学课程列表并且需要创建一个时间表以使课程不会发生冲突,那将是一项非常困难的任务(复杂性方面).但是,根据提议的计划,您可以轻松验证其正确性.
加密领域的另一个重要例子:给定一个数字,它是两个非常大的素数相乘的结果,很难根据结果找到那些素数.但是,给定两个数字,检查解决方案非常容易(将它们相乘,比较).
我故意选择NP中的示例而不是P中的示例(即难以找到解决方案的问题),以便您可以理解其中的差异.所有容易解决的问题也很容易验证 - 只需要解决和比较.也就是说,P是NP的子集.