一千萬個為什麽

搜索

多項式層次結構周圍的符號


我是“計算復雜性”的新手,因此我對以下一些練習有足夠的問題:

請記住:$ \ text {PH}:= \ bigcup_ {i} \ Sigma_i $

     

顯示:

     

$ \ bullet \ bigcup_ {i}(\ Sigma_i \ cup \ Pi_i \ cup \ Delta_i)= \ bigcup_ {i} \ Sigma_i = \ bigcup_ {i} \ Pi_i = \ bigcup_ {i} \ Delta_i $

     

$ \ bullet \ forall k \ in \ mathbb {N}(\ Sigma_k = \ Pi_k \ Rightarrow \ text {PH} = \ Sigma_k)$

我試圖讓自己熟悉多項式層次結構,但一方面我不明白符號$ \ Delta,\ Sigma,\ Pi $的含義另一方面我不知道如何解決實際運動。

請問有人可以給我一些幫助嗎?

最佳答案

$ \ newcommand {\ P} {\ mathsf {P}} \ newcommand {\ PH} {\ {mathsf PH}} $ $ \ newcommand {\ SUM} [1] {\西格瑪_ {#1} ^ {\ P}} \ newcommand {\ PROD} [1] {\裨_ {#1} ^ {\ P}} $ $ \ newcommand {\ DELTA} [1] {\德爾塔_ {#1} ^ {\ P}} $ $ \ newcommand {\ NP} {\ {mathsf NP}} \ newcommand {\ CONP} {\ {mathsf CONP}} $ 來自評論:

為什麽$ \ SUM {1} = \ NP $?

使用證書/證據回憶$ \ NP $的定義:

語言$ L $在$ \ NP $中,如果存在多時間TM $ M $和多項式$ q $,那麽在L \ iff \中的$ x \存在於\ {0, 1 \} ^ {q(| x |)} \ M(x,u)= 1 $$

這也正是$ \ SUM {1} $的定義。在$ \ NP $的情況下,它是一個存在主義($ \ exists $)量詞。現在,存在量詞的否定是通用量詞($ \ forall $)。如果我們換掉$ \ NP $的證書定義中的量詞,我們在L \ iff \ forall u \ in \ {0,1 \} ^ {q(| x |)} \ M(x)中有$ x \ ,u)= 1 $$這正是$ \ coNP $(在層次結構中表示為$ \ PROD {1} $)!通過允許更多(交替)量詞,我們看到$ \ PH $只是對此的概括。

對於第一個子彈:

$ \ bigcup_ {i}(\ SUM {i} \ cup \ PROD {i} \ cup \ DELTA {i})= \ bigcup_ {i} \ SUM {i} = \ bigcup_ {i} \ PROD { i} = \ bigcup_ {i} \ DELTA {i} $

草圖:顯示$ \ SUM {i} \ subseteq \ PROD {i + 1} \ subseteq \ SUM {i + 2} $是很簡單的。理由是你可以簡單地“忽略”驗證TM中的主要量詞。同樣,我們看到$ \ SUM {i} \ subseteq \ DELTA {i + 1} \ subseteq \ SUM {i + 1} $。同樣,這可以解釋,因為$ \ DELTA {i + 1} $和$ \ SUM {i + 1} $都有oracle訪問$ \ SUM {i} $,區別在於$ \ SUM {i + 1} $是基於$ \ NP $的機器,而$ \ DELTA {i + 1} $是基於$ \ P $的機器。

使用子集關系,我們看到所有整數的並集將涵蓋所有情況。

現在為你的第二個子彈:

$ \ forall k \ in \ mathbb {N} \ \ \ SUM {k} = \ PROD {k} \ Rightarrow \ PH = \ SUM {k} $

證明:這可以通過$ k $的歸納來顯示。對於我們的基本情況,讓$ k = 1 $並觀察如果$ \ SUM {1} = \ PROD {1} $則會發生崩潰。要看到這一點,讓$ Q_1,\ cdots,Q_i $成為層次結構中某個級別$ i $的交替量詞。由於$ \ SUM {1} = \ PROD {1} $,我們可以使用存在量詞替換序列中的每個通用量詞,從而導致$ \ exists u_1,\ cdots,\ exists u_i $。但是根據量詞的定義,我們可以將它減少到單個$ \ exists \ langle u_1,\ cdots,u_i \ rangle $,它正好是$ \ SUM {1} $。

現在假設這適用於低於$ k $的所有值。給定級別$ \ SUM {k} $我們可以將其量詞分解為兩部分,初始$ \存在u_1 $和以下交替序列$ \ forall u_2,\ cdots,Q_ {k} u_ {k} $,其中$ Q_ {k} $是$ \ exists $或$ \ forall $,具體取決於$ k $是奇數還是偶數。觀察這個序列正好是$ \ PROD {k-1} $,我們的假設等於$ \ SUM {k-1} $。通過替換和組合初始術語,我們有$$ \ exists \ langle u_1,u_2 \ rangle,\ cdots,Q_ {k} u_ {k} $$這真的只有$ k-1 $條款!因此發生崩潰。

轉載註明原文: 多項式層次結構周圍的符號

猜你喜歡