洛瓦茲局部引理是組合數(shù)學(xué)和概率論中的重要工具,其最主要的用途之一是證明當(dāng)約束之間"弱相關(guān)"時,滿足復(fù)雜約束的組合對象存在.自從1975年Erdos和Lovasz提出洛瓦茲局部引理以來,局部引理在組合數(shù)學(xué)、理論計算機(jī)和物理學(xué)等領(lǐng)域已經(jīng)有了很多應(yīng)用.近年來,為了擴(kuò)展局部引理的應(yīng)用范圍,人們提出了很多新版的局部引理,尤其是在構(gòu)造版本局部引理上取得了重大的突破.本文將綜述局部引理近年來最新的研究進(jìn)展,包括幾種最主要的局部引理變種以及它們在計算機(jī)科學(xué)和物理學(xué)中的應(yīng)用.特別的,我們將給出抽象版本、Lopsided版本、變量版本和量子版本局部引理緊的條件,并討論抽象版本緊的條件同統(tǒng)計物理、量子版本緊的條件同量子物理之間的聯(lián)系.同時,我們還將以布爾可滿足性問題和量子可滿足性問題為例,說明局部引理在證明問題有解、找到問題的解以及對問題的解進(jìn)行計數(shù)和采樣等方面的應(yīng)用. 

【文章頁數(shù)】：17 頁


本文編號：3667841