邵 帅


Email: shao10@ustc.edu.cn

个人主页：http://staff.ustc.edu.cn/~wwwucuc/ 

主要研究方向：理论计算机科学及其与统计物理、量子理论的交叉方向


邵帅，中国科大计算机学院特任教授、博士生导师。2014年本科毕业于中国科大少年班学院华罗庚班，2020年博士毕业于威斯康星大学麦迪逊分校计算机系，就读期间还曾获数学硕士及计算机硕士学位。之后分别在牛津大学及爱丁堡大学从事博士后工作，在牛津工作期间同时被选为Wolfson学院初级研究员。主要研究领域为理论计算机科学，同时涉及其与统计物理、量⼦理论的交叉⽅向。近年来，在精确计数的复杂度分类，近似计数算法与相变现象，量⼦纠缠态等价类分类等⽅⾯取得了一定研究成果，在领域权威期刊和顶级国际会议上发表多篇论文。


导师选题：

边约束满足问题的计算复杂性分类研究能在多项式时间内能验证解的正确性的判定问题称作NP问题，能在多项式时间内求解的判定问题称作P问题。NP问题是否都是P问题？这便是千禧年七大数学难题之一：P vs NP。该问题也是理论计算机科学领域内的著名难题。 P vs NP是针对判定问题而言的。判定问题可以自然地推广到计数问题（计算解的个数）。每个NP问题都有其对应的计数版本，这些问题构成集合#P。FP指的是#P中可在多项式时间内求解的问题。FP vs #P（即是否#P类中的每个计数问题都可在多项式时间内求解）同样是理论计算机科学中一个十分重要的根本问题。大多数研究者相信P≠NP或FP≠#P。在此假设下，著名的Ladner定理表明：存在既不是P也不是NPC的NP问题。然而人们发现，对于某个问题框架下所有的判定或计数问题，其计算复杂性要么是最简单的（P或FP），要么是最难的（NP难或者#P难），不存在中间地带。目前研究者们不断地对包含问题越来越广泛的问题框架证明计算复杂性二分定理，进而探索使这类二分定理成立的问题框架的“极限”在哪里。这其中最为广泛研究，成果也最为瞩目的问题框架便是约束满足问题（Constraint   Satisfaction Problem, CSP）。约束满足问题（CSP）广泛来源于逻辑学、组合学、物理学等领域。它是SAT问题的自然推广，同时包含了诸如独立集、地图染色等诸多有着广泛应用的基础问题。CSP问题的计数版本称作#CSP。目前，对于CSP和#CSP，完备的计算复杂性二分定理均已被证明。然而CSP框架仍有一定局限，很多非常基础的著名问题并不能被CSP框架所涵盖，这其中最为典型的例子就是图的完美匹配问题。判定图是否存在完美匹配可被著名的Edmonds’Blossom算法解决；其在一般图上的计数问题，是第一个被证明的#P完全问题；而其在平面图上的计数问题，则可被统计物理中著名的FKT算法在多项式时间内解决。因为图的匹配问题蕴含着这些如此不平凡的算法和深刻的计算复杂性结果，其重要性不言而喻。本课题将致力于研究一类比CSP问题更加广泛的问题框架边约束满足问题（Edge Constraint Satisfaction Problem, Edge-CSP），并探索其在判定、优化及计数问题下的计算复杂性分类。