一類特殊的實數集分裂問題的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，b_j，r_ij}，其中1≤i≤m，1≤j≤m，i，b_j>表示頂點a_i和b_j之間的邊r_ij，表示邊i，b_j>的權值。二分圖的最大權匹配就是尋找到一種匹配，使得權值之和最大。

現在說明怎么把加權完全二分圖G轉換成帶有權值的完全無向圖G′=(V′，E′)。G中的頂點對應于G′中的頂點，E中的任意一條邊i，b_j，>對應于G′中連接頂點a_i和b_i的一條邊，該邊的權值為－r_ij在G中，沒有邊連接的任意兩個節點，在G′中均有邊連接，這類邊的權值為一個正數，不妨設為MAX。例如，當加權完全二分圖為圖1時，圖2表示了這種構造。為證明歸約滿足要求，需要證明在G中獲得二分圖的最大權匹配時，權值和為P當且僅當在完全圖G′中，滿足要求的這L條邊的權值之和為－p。反證法，易證。由于加權完全二分圖的最大權匹配問題為NP難問題，故定理1成立。

3 總結

本文提出了一種新的優化問題一實數集分裂問題，并給出了該問題的一種特殊情況，通過在多項式時間內二分圖的最大權問題可規約到這種特殊的實數集分裂問題，從而證明了該問題屬于NP難問題。