關于在線性條件下NP≠P的證明

樊雪雙 李云娟

1.西安思源學院基礎部 陜西西安 710038；2.瑪普阿大學研究生院 菲律賓馬尼拉 999005

本文將利用命題公式中所含有的自由變元總次數來刻畫命題公式的最簡形式，且證明命題公式所含有的邏輯門個數是否可轉化為多項式的等價于命題公式中所含有的自由變元總次數是否可轉化為多項式。

1 基本概念及基本定理

首先給出一些必備的概念與定理。

定義1，，…，，…稱為自由變元集序列，其中為自由變元的集合，且對于任意=1，2，……有?+1，記為{}。

定義2 對于任意，若問題真假由中的自由變元的賦值所決定，則稱是上的一個問題。對于任意，其對應的命題公式記為。命題公式序列，，…，，…稱為問題的公式序列，記為{}。

定義3 公式中自由變元的總次數稱為的勢，記為‖‖。

定義4 設公式序列{}，若存在關于的多項式()使得‖‖≤()，則稱公式序列{}是勢多項式的。

定義5 設公式序列{}和{}，對于任意都有?，則稱公式序列{}和{}邏輯等價。

定義6 設公式序列{}，若存在與之邏輯等價且為勢多項式的序列，則稱{}是可勢多項式的。

定義6設公式序列{}，若存在與之邏輯等價且為聯結詞多項式的序列，則稱{}是可聯結詞多項式的。

定義7 給定公式，若公式滿足以下兩條，則稱為的一個極小式。

與邏輯等價。

(2)不存在與邏輯等價的公式，使得‖‖<‖‖。

定義8對于命題公式，把蘊含的原子合取式稱為的一個解。進一步，若不存在的解，使得?，且‖‖<‖‖，則稱為的一個極簡解。

為了對命題公式進行等價轉換，引入強Demorgen轉換。

定義9 對命題公式可多次利用Demorgen律，使得邏輯非下不再含有析取和合取，然后可再利用雙重否定律，使得公式中每個自由變元上最多含有一個邏輯非，稱該轉換過程為強Demorgen轉換。經過強Demorgen轉換所得到的公式記為()。

顯然，對于任意公式，‖‖=‖()‖。

下面說明對于任意公式序列可勢多項式與可聯結詞多項式是等價的。

定理3 對于任意公式序列{}，其為可聯結詞多項式的等價于其為可勢多項式的。

根據定理1，把判斷公式序列是否為可聯結詞多項式的轉化為判斷其是否為可勢多項式的。

2 類皇后問題Simqueen(n)

下面給出類皇后問題Simqueen(n)，并給出描述該問題的公式序列。

Simqueen(n)：對于一個階0-1矩陣(元素全部為0或1)，是否可以從不同行，且不同列找到個元素全部為1。

Simqueen(n)的公式：

顯然，當，…，為1，2…，的一個全排序時，1∧2…∧為的一個極簡解。

引理1對于與Simqueen(n)的公式邏輯等價的公式，利用分配律把()展成的析取范式記為∨，若為可滿足式，則具有以下性質：

至少存在一個的極簡解∧…∧，其中自由變元，，…，都屬于{|是中不含非的自由變元}。使得?∧…∧。

證明 由于是可滿足式，從而中不含有同一個變元及其非。把原子合取式中出現的自由變元是否帶非分為兩種，把表示為：

構造一個賦值={當在中出現且不帶非，=1；其他=0}。

顯然，|=1，從而()|=1。由于()?，從而|=1，即∨(∧…∧)|=1，至少存在一個極簡解，，…，，使得∧…∧|=1。再由于.和∧…∧都為原子合取式，∧…∧為極簡解且不含非，從而∧…∧中的自由變元只可能是，，…，中的，且?∧…∧。

定理2 Simquee(n)的線性公式序列{}不是可聯結詞多項式的。

證明 假設Simqueen的線性公式序列{}是可聯結詞多項式的。

由定理1可知Simquee(n)的公式序列{}也是可勢多項式的。那么存在勢多項式公式序列{}，其中?且||≤()，()為關于的多項式。

從而假設不成立，Simqueen(n)的線性公式序列{}不是可聯結詞多項式的。

3 關于NP與P的結論

1972年Savage在文獻[10]中證明了電路規模與圖靈機時間之間有一個緊密的關系。

定理3在線性條件下NP≠P。

證明 顯然Simqueen(n)是一個問題，但是由定理2可知Simqueen(n)的線性公式序列{}不是可聯結詞多項式的，從而類皇后問題在線性條件下不能通過邏輯門的數量為多項式規模的電路來解決，從而在線性條件下≠。

4 Simqueen(n)的極小式

下面給出階變元行列式的展開式和極小展開式概念。

記階0-1變元矩陣為。

稱(∧)∨(∧)為的極小展開式。

定義11對于任意，展開式和極小展開式定義如下：

在中取定個行：1≤<<…<≤，稱下面公式為的一個展開式，

把勢取最小值的展開式稱為的一個極小展開式，記為()。

解 對于，的取值可以為1，2。

當=1時，按第一行展開，其展開式為:

(∧((∧)∨(∧)))∨(∧((∧)∨(∧)))∨(∧((∧)∨(∧)))

當=2時，按第一，二行展開，其展開式為：

(((∧)∨(∧))∧)∧(((∧)∨(∧))∧)∧(((∧)∨(∧))∧)

由于=1，=2，上面兩個展開式的勢都為15，所以上面兩個展開式都為的極小展開式。

由于的任意展開式的主范式必含有且只含有的所有路徑(路徑中自由變元的順序可能不同)，從而的任意展開式必與邏輯等價。接下來，考慮的極小展開式的勢，記極小展開式的勢為()，即()=‖()‖。

其中(1)=1顯然成立。

例2求(4)的值。

取最小值15，從而(3)=15。

雖然關于()的關系式沒有給出，但可以考慮它的取值范圍。下面給出()的一個下限估計。

猜想1：Simqueen(n)的極小式等于()。