一类特殊的实数集分裂问题的NP难度证明

李小龙　段雪峰　徐增敏

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

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

中图法分类号：TP393

文献标识码：A

0引言

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

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

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

1问题定义

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

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

实数集分裂问题：对于一个由n×m个实数组成的集合，若将其平均分配到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={a₁，a₂…，a_m}和B=(b₁，b₂，…，b_m)，E={i