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

摘要：

洛瓦兹局部引理是组合数学和概率论中的重要工具,其最主要的用途之一是证明当约束之间“弱相关”时,满足复杂约束的组合对象存在.自从1975年Erd(o)s和Lovász提出洛瓦兹局部引理以来,局部引理在组合数学、理论计算机和物理学等领域已经有了很多应用.近年来,为了扩展局部引理的应用范围,人们提出了很多新版的局部引理,尤其是在构造版本局部引理上取得了重大的突破.本文将综述局部引理近年来最新的研究进展,包括几种最主要的局部引理变种以及它们在计算机科学和物理学中的应用.特别的,我们将给出抽象版本、Lopsided版本、变量版本和量子版本局部引理紧的条件,并讨论抽象版本紧的条件同统计物理、量子版本紧的条件同量子物理之间的联系.同时,我们还将以布尔可满足性问题和量子可满足性问题为例,说明局部引理在证明问题有解、找到问题的解以及对问题的解进行计数和采样等方面的应用.

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

所属期刊栏目：50

分类号：Q949;TP3;S7

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;中国科学院战略性先导科技专项;中国科学院王宽诚率先人才计划产研人才扶持项目

在线出版日期：2020-12-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共17页

页码：1680-1696