一類特殊的實數(shù)集分裂問題的NP難度證明

李小龍　段雪峰　徐增敏

摘要：定義了實數(shù)集分裂問題，并給出了一類特殊的實數(shù)集分裂問題。通過構造與二分圖的最大權問題相應的圖形模型，證明了這種特殊的實數(shù)集分裂問題是NP難的。

關鍵詞：實數(shù)集合分裂問題NP難

中圖法分類號：TP393

文獻標識碼：A

0引言

在多項式時間內，由確定型圖靈機(deterministic Turing ma-chine，簡稱DTM)可以解決的問題稱為P問題；如果一個問題，其解法在多項式時間內可以由一個非確定型圖靈機(nondeterminsticTunring machine，簡稱NTM)實現(xiàn)，那么，此問題屬于NP問題。如果所有的NP問題在有限步內(在多項式規(guī)約時間內)可相互規(guī)約問題巧則稱為NP難題(NP-Hard)。如果某個問題是NP-hard的，同時又是NP問題，那么稱其為NP完全(NP-complete，簡稱NPC)問題。NP難是NP類中最難的一類問題。NP難理論的研究在實踐中有著重要的指導作用，在算法設計和分析過程中，如果證明某問題是NP難的，這就意味著在多項式時間內找到該問題的精確解是非常難的，或者說是不可能的。因此，對于NP難問題，最好是去尋找近似解法，尋找設計在多項式時間可完成的近似解算法。

本文提出了一種新的優(yōu)化問題—實數(shù)集分裂問題，并給出了該問題的一種特殊情況，證明了這種特殊的實數(shù)集分裂問題屬于NP難問題，基本思路是：通過引入二分圖的最大權問題，而這種特殊的實數(shù)集合分裂問題可在多項式時間內相互規(guī)約成二分圖的最大權問題，從而證明這種特殊的實數(shù)集分裂問題是NP難的。

本文其余部分組織如下：第1節(jié)對實數(shù)集分裂問題進行了定義，并給出了一種特殊情況。第2節(jié)證明了該問題屬于NP難問題。第3節(jié)總結全文。

1問題定義

在定義實數(shù)集分裂問題之間，我們首先給出實數(shù)集之間的距離的定義。

實數(shù)集之間的距離：對于兩個均由n個數(shù)組成的集合，若存在著一種匹配，使其匹配數(shù)之差的絕對值之和最小，則稱這個值為實數(shù)集之間的距離。

實數(shù)集分裂問題：對于一個由n×m個實數(shù)組成的集合，若將其平均分配到n個子集中，使其每個子集包含的元素個數(shù)均為m個。問題是：如何分配實數(shù)，使得n個子集兩兩之間的距離之和最小。

對于實數(shù)集分裂問題，我們首先考慮n=2的情況，接下來我們證明n=2時實數(shù)集分裂問題是NP難的。

2問題是NP難問題的證明

定理1：當n=2時，實數(shù)集分裂問題是NP難問題。

證明：首先我們進行一下問題轉換。如果將實數(shù)集的元素對應于頂點，元素之間的差的絕對值對應于邊的權值，實數(shù)集可以構成一個帶有權值的完全無向圖，其中頂點個數(shù)為2m，邊的個數(shù)為m(2m-1)。傳感器網(wǎng)絡的極大相似分布問題等價于在對應的完全無向圖中找出m條邊，這m邊滿足如下條件：①每個頂點有且僅與其中的一條邊相連；②這m條邊的權值之和最小。

設G=(V，E)是一個加權完全二分圖，兩邊的頂點分別為A={a₁，a₂…，a_m}和B=(b₁，b₂，…，b_m)，E={i