洛瓦兹局部引理的新变种及其应用  

New versions of Lovász Local Lemma and their applications

作　　者：何昆 孙晓明[3,4] Kun HE;Xiaoming SUN(School of Computer and Software,Shenzhen University,Shenzhen 518061,China;Shenzhen Institute of Computing Sciences,Shenzhen 518109,China;Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]深圳大学计算机与软件学院,深圳518061 [2]深圳计算科学研究院,深圳518109 [3]中国科学院计算技术研究所,北京100190 [4]中国科学院大学,北京100049

出　　处：《中国科学：信息科学》2020年第11期1680-1696,共17页Scientia Sinica(Informationis)

基　　金：国家自然学基金(批准号:61433014,61832003,61761136014,61872334,61801459);中国科学院战略性先导科技专项(B类)(批准号:XDB28000000);中国科学院王宽诚率先人才计划卢嘉锡国际团队项目资助。

摘　　要：洛瓦兹局部引理是组合数学和概率论中的重要工具,其最主要的用途之一是证明当约束之间"弱相关"时,满足复杂约束的组合对象存在.自从1975年Erdos和Lovasz提出洛瓦兹局部引理以来,局部引理在组合数学、理论计算机和物理学等领域已经有了很多应用.近年来,为了扩展局部引理的应用范围,人们提出了很多新版的局部引理,尤其是在构造版本局部引理上取得了重大的突破.本文将综述局部引理近年来最新的研究进展,包括几种最主要的局部引理变种以及它们在计算机科学和物理学中的应用.特别的,我们将给出抽象版本、Lopsided版本、变量版本和量子版本局部引理紧的条件,并讨论抽象版本紧的条件同统计物理、量子版本紧的条件同量子物理之间的联系.同时,我们还将以布尔可满足性问题和量子可满足性问题为例,说明局部引理在证明问题有解、找到问题的解以及对问题的解进行计数和采样等方面的应用.Lovász Local Lemma(LLL)is an important tool in combinatorics and probability theory.It can be used to show the existence of combinatorial objects meeting a collection of criteria as long as the criteria are weakly dependent.It was first proposed by Erdos and Lovász in 1975.Since then,many applications of LLL have been found in combinatorics,theoretical computer science,and physics.Recently,several new versions of LLL have been proposed.Constructive LLL is an especially big breakthrough in theoretical computer science that has attracted lots of attention.In this paper,we will review recent progress in LLL research,including new versions of LLL and their applications.We will precisely define and differentiate among abstract LLL,lopsided LLL,variable LLL,and quantum LLL.We will also provide connections between abstract LLL and statistical physics,as well as between quantum LLL and quantum physics.LLL can be used to prove the existence of solutions,find solutions efficiently,count the number of solutions,and sample a solution uniformly at random.We will also illustrate these applications of LLL with the SAT problem and the quantum SAT problem.

关 键 词：洛瓦兹局部引理 变量版本局部引理 量子版本局部引理 构造版本局部引理 Shearer界 

分 类 号：O211[理学—概率论与数理统计] O157[理学—数学]