NP是指非确定性多项式（non-deterministicpolynomial）。非确定性指可用一定数量的运算去解决多项式时间内可解决的问题。
推销员旅行问题（TravelSalemanProblemorTSP）：从香港经过n个城市，最后返回香港。任意两市都有飞机直达，票价不等。公司只报销C元，是否存在行程安排，使得遍历所有城市且总路费小于C？如果你任意给出一个行程安排，很容易算出旅行总开销。要知道总路费小于C的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。
“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。对其中一个问题存在有效算法时，每个问题都会有有效算法。
倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求近似算法。