项目名称: 参数复杂性、SAT求解器和树宽度

项目编号: No.61373029

项目类型: 面上项目

立项/批准年度: 2013

项目学科: 自动化技术、计算机技术

项目作者: 陈翌佳

作者单位: 上海交通大学

项目金额: 76万元

中文摘要: 参数复杂性是目前在理论计算机科学中非常活跃的一个分支。相比以多项式时间算法为核心的经典算法和复杂性理论,通过允许超多项式行为局限于某些小参数的指数时间算法,它为算法设计提供了更多的灵活性和复杂性分析更为精细的框架。我们计划研究以下的一些基于树宽度的比较新颖的参数复杂性问题。1)SAT问题在工业界有着极为重要的应用。虽然其在一般意义上是NP难的,但许多SAT问题的求解器在实际使用中非常高效。我们计划从参数复杂性角度来分析这些SAT求解器。特别的是,我们希望理解对于实际应用中出现的SAT实例是否存在一些隐藏的参数,它们导致求解器的高效。该研究一个很好的起点就是树宽度有界的实例。2)对于很多参数计算问题,树宽度给出了高效可解和计算困难间的精确边界。但还有一些关于树宽度及其相关的算法问题仍有待解决。如:我们希望研究删点操作对树宽度的影响;针对程序语言的研究,我们试图给出树宽度有界图的公理系统;为了理解monadic二阶逻辑(MSO)的表达能力,我们计划考察独立于序的MSO。

中文关键词: 参数复杂性;固定参数可解;树宽度;近似;复杂性类

英文摘要: Parameterized complexity is a very active subfield of theoretical computer science. Compared to classical theory of algorithms and complexity which is built on the central notion of polynomial time computability, it provides more flexibility for algorithm

英文关键词: parameterized complexity;fixed-parameter tractable;treewidth;approximation;complexity classes

成为VIP会员查看完整内容
0

相关内容

专知会员服务
207+阅读 · 2021年8月2日
专知会员服务
24+阅读 · 2021年7月22日
专知会员服务
21+阅读 · 2021年6月26日
【干货书】数值Python计算,Numerical Python,709页pdf
专知会员服务
102+阅读 · 2021年5月30日
专知会员服务
41+阅读 · 2020年9月25日
【ICML2020】机器学习无参数在线优化,294页ppt
专知会员服务
53+阅读 · 2020年8月1日
浅谈点击信号对搜索的影响
夕小瑶的卖萌屋
0+阅读 · 2022年1月18日
【博士论文】基于冲量的加速优化算法
专知
7+阅读 · 2021年11月29日
不仅是观众!2021 Google 开发者大会听你说
TensorFlow
0+阅读 · 2021年9月27日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月19日
Convergence of the Discrete Minimum Energy Path
Arxiv
0+阅读 · 2022年4月15日
Heterogeneous Graph Transformer
Arxiv
27+阅读 · 2020年3月3日
Arxiv
11+阅读 · 2018年5月21日
小贴士
相关VIP内容
专知会员服务
207+阅读 · 2021年8月2日
专知会员服务
24+阅读 · 2021年7月22日
专知会员服务
21+阅读 · 2021年6月26日
【干货书】数值Python计算,Numerical Python,709页pdf
专知会员服务
102+阅读 · 2021年5月30日
专知会员服务
41+阅读 · 2020年9月25日
【ICML2020】机器学习无参数在线优化,294页ppt
专知会员服务
53+阅读 · 2020年8月1日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
微信扫码咨询专知VIP会员