COMP6741

Parameterized and Exact Computation

课程介绍： 本课程重点介绍精确解决NP难计算问题的算法。由于对于这些问题中的任何一个都不知道多项式时间算法， 因此算法的运行时间将具有对输入大小或输入的一些其他参数的超多项式依赖性。 第一部分介绍了在最坏的情况下解决NP难题的算法技术，证明其比蛮力要快得多，例如分支算法，跨子集的动态编程，包含排除，局部搜索以及度量和征服。我们还将看到算法的下限，以及假设（强）指数时间假设的情况下如何排除某些运行时间。 第一部分介绍了“默认”算法，在不了解实例即将解决的实例的情况下将使用该算法，而第二部分则承认实例的复杂度不仅取决于其大小n。参数k与每个实例相关联，并且参数化复杂度框架旨在设计固定时间算法，其可计算函数f的运行时间为f（k）* poly（n）。这为通过分支，颜色编码，迭代压缩和内核化（预处理）之类的技术获得的参数较小值提供了有效的算法。我们还将看到在复杂性理论假设的约束下，固定参数无法处理且无法多项式化的问题。