双变量含公理的一阶逻辑模型计数
Speaker
邝启鹏, 香港大学博士生
Time
2025-03-11 16:00:00 ~ 2025-03-11 17:00:00
Location
上海交通大学软件大楼专家楼1319会议室
Host
杨宽
Abstract
一阶逻辑模型计数是统计关系学习的重要基础工具，近年也逐渐应用于神经符号人工智能和计数组合学。如果一个一阶逻辑公式的模型计数能在关于域大小的多项式时间内计算，则称之为“域可提升”。已有研究表明，当一阶逻辑公式含有两个变量时是域可提升的，而含有三个变量时则不是域可提升的，而对双变量一阶逻辑附加以特定的作用于谓词的公理，可以拓展其表达能力并且保留域可提升性。
本次报告将会介绍双变量含公理一阶逻辑模型计数的最新成果，其一，对于单个公理的情况，仿照图多项式的思路定义模型计数多项式，可以得到一种通用的域可提升算法；其二，对于多个公理的情况，可证明含两个线性关系公理的模型计数是困难的。最后，本次报告还将讨论一阶逻辑模型计数各种可能的发展方向，及其与计数复杂性类 #P1 的关系。
Bio
邝启鹏是香港大学博士三年级学生，师从 Hubert Chan 副教授，研究方向为计数、采样和一阶逻辑，本科毕业于中山大学计算机科学与技术专业。