实数集分裂问题的NP难度证明

实数集分裂问题的NP难度证明

刘洋李小龙

刘洋李小龙（桂林电子科技大学管理学院桂林电子科技大学数学与计算科学学院）

摘要：定义了实数集分裂问题，通过构造与二分图的最大权问题相应的图形模型，证明了实数集分裂问题是NP难的。

关键词:实数集合分裂问题NP难

中图法分类号：TP393文献标识码：A

0引言

在多项式时间内，由确定型图灵机(deterministicTuringmachine，简称DTM)可以解决的问题称为P问题；如果一个问题，其解法在多项式时间内可以由一个非确定型图灵机(nondeterministicTuringmachine，简称NTM)实现，那么，此问题属于NP问题。如果所有的NP问题在有限步内（在多项式规约时间内）可相互规约问题巧则称为NP难题（NP-Hard）[1]。如果某个问题是NP-hard的，同时又是NP问题，那么称其为NP完全(NP-complete，简称NPC)问题。NP难是NP类中最难的一类问题。NP难理论的研究在实践中有着重要的指导作用，在算法设计和分析过程中，如果证明某问题是NP难的，这就意味着在多项式时间内找到该问题的精确解是非常难的，或者说是不可能的。因此，对于NP难问题，最好是去寻找近似解法，寻找设计在多项式时间可完成的近似解算法[2]。

本文提出了一种新的优化问题——实数集分裂问题，并给出了该问题的一种特殊情况，证明了这种特殊的实数集分裂问题属于NP难问题，基本思路是：通过引入二分图的最大权问题，而二分图的最大权问题可在多项式时间内相互规约成这种特殊的实数集合分裂问题，从而证明这种特殊的实数集分裂问题是NP难的。在此基础上，证明了实数集分裂问题是NP难的。

本文其余部分组织如下：第1节对实数集分裂问题进行了定义,并给出了一种特殊情况。第2节证明了该问题属于NP难问题。第3节总结全文。

1问题定义

在定义实数集分裂问题之间，我们首先给出实数集之间的距离的定义。

实数集之间的距离：对于两个均由n个数组成的集合，若存在着一种匹配，使其匹配数之差的绝对值之和最小，则称这个值为实数集之间的距离。

实数集分裂问题：对于一个由n×m个实数组成的集合(n≥2)，若将其平均分配到n个子集中，使其每个子集包含的元素个数均为m个。问题是：如何分配实数，使得n个子集两两之间的距离之和最小。对应的值我们定义为实数集的最小分裂度。

对于实数集分裂问题，我们首先考虑n=2的情况，接下来我们证明n=2时实数集分裂问题是NP难的。

2问题是NP难问题的证明

定理1：当n=2时，实数集分裂问题是NP难问题。

证明：首先我们进行一下问题转换。如果将实数集的元素对应于顶点，元素之间的差的绝对值对应于边的权值，实数集可以构成一个带有权值的完全无向图，其中顶点个数为2m，边的个数为m(2m-1)。传感器网络的极大相似分布问题等价于在对应的完全无向图中找出m条边，这m边满足如下条件:①每个顶点有且仅与其中的一条边相连；②这m条边的权值之和最小。

设G=(V，E)是一个加权完全二分图，两边的顶点分别为A={a1，a2，…，am}和B={b1，b2，…，bm}，E={<ai，bj>，ri，j}，其中1≤i≤m，1≤j≤m，<ai，bj>表示顶点ai和bj之间的边，ri，j表示边<ai，bj>的权值。二分图的最大权匹配就是寻找到一种匹配，使得权值之和最大。

现在说明怎么把加权完全二分图G转换成带有权值的完全无向图G′=(V′，E′)。G中的顶点对应于G′中的顶点，E中的任意一条边<ai，bj>对应于G′中连接顶点ai和bj的一条边，该边的权值为－ri，j。在G中，没有边连接的任意两个节点，在G′中均有边连接，这类边的权值为一个正数，不妨设为MAX。例如，当加权完全二分图为图1时，图2表示了这种构造。为证明归约满足要求，需要证明在G中获得二分图的最大权匹配时，权值和为P当且仅当在完全图G′中，满足要求的这L条边的权值之和为-P。反证法，易证。由于加权完全二分图的最大权匹配问题为NP难问题，故定理1成立。

定理2：实数集分裂问题是NP难的。

证明:对于一个包含了2m个元素的实数集，不妨假设当实数集达到极大相似分布时，此时得到的子集分别为A={a1，a2，…，am}和B={b1，b2，…，bm}，实数集的最小分裂度对应的值为P。

现在说明怎么把一个包含了2m个元素的实数集转成n×m个元素的实数集N′。该n×m个节点的实数集由以下n×m个元素组成:{a'1，a'2，…，a'm，b'1，1，b'2，1，…，b'm，1，…，b'1，n-1，b'2，n-1，…，b'm，n-1}。元素ai对应于元素a'i，元素bi对应于元素b'i，j，其中1≤i≤n，1≤j≤m-1，此时实数集N′的最小分裂度为(n-1)P。

为证明该归约满足要求，需要证明对于实数集N，当n=2时，实数集的最小分裂度为P当且仅当对于实数集N′，分组数为n时，实数集N′的最小分裂度为(n-1)P。首先证明充分性，由上可知，对于实数集N，将集合分成{a1，a2，…，am}和{b1，b2，…，bm}这两组时，此时实数集之间的距离最小，为P。显然实数集N′的分组情况为{a'1，a'2，…，a'm}，{b'1，1，b'2，1，…，b'm，1}，…，{b'1，n-1，b'2，n-1，…，b'm，n-1}也是最小的，因为{b'1，i，b'2，i，…，b'm，i}与{a'1，a'2，…，a'm}之间的距离等于{a1，a2，…，aL}和{b1，b2，…，bL}的距离，当i≠j，{b'1，i，b'2，i，…，b'm，i}和{b'1，j，b'2，j，…，b'm，j}之间的距离均为0。因此对于子集个数n时，实数集的最小分裂度为(n-1)P。证明必要性可参照充分性的证明过程，易得证，故省略。

由定理1可知，这种特殊的实数集分裂问题是NP难的，且在多项式时间内该问题可归约到一般的实数集分裂问题，因此说明后者是NP难的。

3总结

本文提出了一种新的优化问题——实数集分裂问题，通过在多项式时间内二分图的最大权问题可规约到一般的实数集分裂问题，从而证明了实数集分裂问题属于NP难问题。

参考文献：

[1]CormenTH,LejsersonCE,RivestRL,SteainC.IntroductiontoAlgorithms.2nded.,TheMITPress,2001.

[2]SipserM.IntroductiontotheTheoryofComputation.CourseTechnology.2005.

本文受广西自然科学基金(0991079)，桂林电子科技大学自然科学研究基金(UF08026Y)资助。

作者简介：

刘洋（1981-），女，本科，助教，主要研究方向为工程管理等。

李小龙（1981-），男，博士，主要研究方向为传感器网络等。