Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)
复制标题
指数算法：超越多项式时间的算法和复杂性（Dagstuhl 研讨会 13331）
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
T. Husfeldt;R. Paturi;G. Sorkin;Ryan Williams
本报告记录了Dagstuhl研讨会13331“指数算法：多项式时间以外的算法和复杂性”的程序和结果。在实践中，通常用最坏情况指数时间复杂度算法来解决问题。对于给定的问题，找到最快的算法是很有趣的，无论是多项式的，指数的，还是介于两者之间的。研讨会的重点是比np完备性更细粒度的复杂性概念，以及理解问题的确切复杂性。该报告提供了研讨会的基本原理，并记录了研讨会上的演讲。报告注意到在过去同一主题的讲习班上提出的未解决问题的进展情况。它还报告了引用前一次研讨会上的演讲的结果集合。该文件收录了研讨会上提出的成果摘要。它还提供了未解决问题的概要。(少)
This report documents the program and the outcomes of Dagstuhl Seminar 13331 "Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time". Problems are often solved in practice by algorithms with worst-case exponential time complexity. It is of interest to find the fastest algorithms for a given problem, be it polynomial, exponential, or something in between. The focus of the Seminar is on finer-grained notions of complexity than np-completeness and on understanding the exact complexities of problems. The report provides a rationale for the workshop and chronicles the presentations at the workshop. The report notes the progress on the open problems posed at the past workshops on the same topic. It also reports a collection of results that cite the presentations at the previous seminar. The docoument presents the collection of the abstracts of the results presented at the Seminar. It also presents a compendium of open problems. (Less)