Simone什么是NPC问题？
的有关信息介绍如下：
在近几十年来，算法复杂性的重要性是与日俱增的： 存在许多还没找到者梁有效算法的问题．也许其中最著名的要数图论中的“旅行推销员问题”，简称“TSP”。即“已给一个n个点的完全图，每条边都有一个长辩滚度，求总长度最短的经过每个顶点正好一次的封闭回路”．Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法．这些问题称为NP难题（NP-Hard或NPH）。迄今为止，这类问题中没有一个找到有效算法．目前倾向于接受NP完全问题（NP-Complet或NPC）和NP难题不存在有效算法这一猜想，认为这类问题首灶运的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法． 计算复杂性理论源于对判定问题算法的研究。 判定问题：其答案不是“是”就是“否”的问题。如，一个图的两顶点之间存在路径吗？判定问题有．三类：P，NP和NPC． P类：已有多项式时间算法的判定问题． NP类：已有指数时间算法的判定问题，包括P类． NPC类：是NP的一个子集，且其中每一个问题均能由NP中的任何问题在多项式时间内转化而成．问题A能在多项式时间内转化为问题B可理解为，问题A有一个算法以问题B的算法为子程序，当把每次对B算法的调用看作一个基本操作（只花常数时间）时，A的这个算法是多项式时间的．
