2012年全国理论计算机科学学术年会(NCTCS2012)于2012年8月18日至19日在美丽的海滨城市海南省海口市召开。此次年会由中国计算机学会主办，海南大学信息科学技术亚洲电竞博彩网站导航
承办，海南省计算机学会和海南软件职业技术亚洲电竞博彩网站导航
协办。虽然赶上了台风“启德”来袭，来自全国各地科研院所和大学的80余名代表还是如期出席了年会。年会特邀了北京大学苏开乐等四名资深教授做了精彩的大会报告。部分代表受邀在“算法”、“逻辑”和“人工智能”三个分组做了分组报告。年会结束时颁发了优秀学生论文奖。
我院崔鹏副教授以Generalized Unique Game Problem为题目做了报告。他的论文已发表在国际期刊Journal of Computational Information Systems上。唯一性游戏问题是一个图上的优化问题，即给定一个边上带字母表排列的图，给图的每个顶点指定字母，使得尽可能多的边上的排列规定映射被满足。唯一性游戏假设(UGC)由美国纽约大学的Khot于2002年提出，近年来得到美国和以色列计算机科学家的高度重视。UGC宣称，在NP不等于P的前提下，对任意长的字母表，唯一性游戏问题难以近似到任意常数范围之内。它是当前国际计算理论界研究的核心问题之一。这个猜测能够成立，将使得一系列组合优化问题甚至任意约束满足问题的不可近似性得到精确的确定。崔鹏副教授通过引入负权，拓展了唯一性游戏问题的研究范围。他定义的GUGP-PWT模型是目前这个问题的自然的和合理的相变模型之一，有助于在研究中采纳更有效的代数方法，并且以此为基础确定这个问题难解性和易解性的相变边界。
唯一性游戏假设是否成立，目前仍没有定论。最近，大多数研究者倾向于认为UGC是不成立的。国际计算理论界公认这个问题的难度很大，距离最终解决还有很大距离。崔鹏副教授经过研究，得出了UGC不成立，除非NP=RP的条件性结果。在计算复杂性理论里，普遍认为NP不等于RP。这就意味着他给出了UGC不成立的强有力证据。崔鹏副教授将于近期公开他的研究论文。