约束满足问题的近似

约束满足问题（CSP）非正式地讲，是一个计算问题，旨在找到从一组值到一组变量的赋值，使得该赋值满足对变量所能取值的一系列给定约束。CSP 是一个足够通用的框架，能够表达广泛的计算问题，同时它保持着丰富的数学结构，因此可以从代数、逻辑、图论和组合学等多个领域汲取技术来处理它。CSP 及其变体的计算复杂性是一个非常活跃的研究领域，存在许多长期悬而未决的问题，并且最近涌现出新的研究方向。 近似是一个特别富有成果的研究领域，其重点是在假设计算精确解在计算上困难的前提下，寻找有效计算 CSP 实例次优解的方法。这可以采取多种不同的形式，例如寻找最大化满足约束数量的解（称为 max-CSP），或寻找在定性较弱的意义上满足所有约束的解（称为 Promise CSP）。该博士项目的一个可能重点是将这两种方法结合起来。然而，学生将有权在约束满足理论的广泛领域内提出和探索自己的研究问题。 成功的候选人将加入一个充满活力的研究人员社区，并有机会在国内和国际会议上展示他们的研究成果。 系里的博士生被鼓励在攻读博士学位的同时从事有偿助教工作。 申请流程 鼓励申请人在正式提交申请之前联系 Silvia Butti 博士（silvia.butti@kcl.ac.uk），内容包括其学术背景、研究兴趣和任何相关的过往经历的摘要。 要被考虑该职位，候选人必须通过 King’s Apply 在线申请系统进行申请。详情请见 [https://www.kcl.ac.uk/informatics/study-with-us/research-degrees] 请申请“Computer Science Research MPhil/PhD (Full-time)”，并在您的申请和所有通信中注明 Silvia Butti 博士为指导教师，并引用项目标题。 请确保在申请表的 Funding 部分添加代码 833。请选择选项 5 ‘I am applying for a funding award or scholarship administered by King’s College London’，并在 ‘Award Scheme Code or Name’ 框中输入该代码。 请准确复制并粘贴该代码。 选拔过程将包括文件预选，如果被选中，随后将发出面试邀请。如果面试成功，将适时发出录取通知。 该奖项面向英国及海外学生开放。该学生奖学金全额涵盖学费、津贴、研究培训与支持补助金。