P与NP问题概念解剖

姜咏江      

把简单问题说复杂了，那叫蒙人；把复杂问题说简单了，那叫学问。

定义1：集合X的一个元素x与集合Y的一个元素y的对应(x，y)称为问题。

定义2：集合X、Y关系确定的问题称为NP类问题，函数（映射）确定的问题称为P类问题。

定理1：集合X、Y的P类问题亦是NP类问题。

证明：若(x，y)∈P，则因函数（映射）是关系的特例，所以(x，y)∈NP。

定理2：集合X、Y的NP类问题亦是P类问题。

证明：假设有x∈X，y∈Y，有问题(x，y)∈NP且(x，y)∈P，则可以定义一个函数（映射）使得(x，y)是该函数（映射）的一个问题。于是就有了(x，y)∈P。

函数或映射的定义域可以一般集合，可以是n维集合上的元素。例如，x是n个数集A={a1,a2,...,an}的幂集的元素，则x的元素和函数的问题为（x，Σa_i）（这里不好表示a_i∈x)。

定义3：若关系确定的问题可用自然数标号，则称此关系是有序关系，问题的标号称为序。

所谓标号，就是问题与自然数集的数能够建立一一对应。

定义4：若函数确定的问题可用自然数标号，则称此函数是有序函数，问题的标号称为序。

定理3：有限元素集合X、Y，X到Y的关系是有序关系。

证明：设集合X有m个元素，集合Y有n个元素，则当x∈X，y∈Y时，互不相同的问题 (x，y) 共有mn个，于是可以建立问题与自然数集N={1,2,...,mn}元素的一一对应。

推论1：有限元素集合X到Y的函数是有序函数。

推论2：以有限集合A的非空子集为元素定义的函数是有序函数。

证明：设集合A的元素有n个，则A的幂集Β有2n-1个非空子集元素。将非空子集用1到2n-1的自然数标号，于是定义在Β上的任意函数的问题与2n-1个从1到2n-1的自然数一一对应。

定义5：有序关系问题按序列表，称为关系真值表。

定义6：有序函数问题按序列表，称为函数真值表。

定义7：寻找附合条件问题的过程，叫做求解。

定理4（多项式时间定理）：m元与k元有限集合间关系求解时间是多项式时间。

证明：设有限集合间关系的序为N={1,2,...,n}，n=mk，问题（a0,y0）是要验证的问题。则依序最多比较n次可以得到是与否的结果。故查找问题（a0,y0,）的时间复杂度是O(n)。

推论3：二有限集合间的函数问题求解时间是多项式时间。

推论4：有限集合到自身的关系求解是多项式时间。

推论5：有限集合到自身的函数求解是多项式时间。

E-mail:accsys@126.com

2014-12-12