關(guān)于在線性條件下NP≠P的證明

樊雪雙 李云娟

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

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

1 基本概念及基本定理

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

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

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

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

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

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

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

定義6設(shè)公式序列{}，若存在與之邏輯等價且為聯(lián)結(jié)詞多項式的序列，則稱{}是可聯(lián)結(jié)詞多項式的。

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

與邏輯等價。

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

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

為了對命題公式進(jìn)行等價轉(zhuǎn)換，引入強Demorgen轉(zhuǎn)換。

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

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

下面說明對于任意公式序列可勢多項式與可聯(lián)結(jié)詞多項式是等價的。

定理3 對于任意公式序列{}，其為可聯(lián)結(jié)詞多項式的等價于其為可勢多項式的。

根據(jù)定理1，把判斷公式序列是否為可聯(lián)結(jié)詞多項式的轉(zhuǎn)化為判斷其是否為可勢多項式的。

2 類皇后問題Simqueen(n)

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

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

Simqueen(n)的公式：

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

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

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

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

構(gòu)造一個賦值={當(dāng)在中出現(xiàn)且不帶非，=1；其他=0}。

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

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

證明 假設(shè)Simqueen的線性公式序列{}是可聯(lián)結(jié)詞多項式的。

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

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

3 關(guān)于NP與P的結(jié)論

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

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

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

4 Simqueen(n)的極小式

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

記階0-1變元矩陣為。

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

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

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

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

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

當(dāng)=1時，按第一行展開，其展開式為:

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

當(dāng)=2時，按第一，二行展開，其展開式為：

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

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

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

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

例2求(4)的值。

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

雖然關(guān)于()的關(guān)系式?jīng)]有給出，但可以考慮它的取值范圍。下面給出()的一個下限估計。

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