参数复杂性理论的研究

参数复杂性是一种较为新颖的复杂性理论框架。它基于以下的考察：很多实际问题的输入蕴含丰富的结构信息，例如对于数据库查询问题，它的输入包含两个部分：一个数据库和一个查询。而我们知道在实际工作中，前者的尺度远比后者要大。因此如果一个指数时间算法的运行时间是前者大小的多项式，那么它仍是可接受的。参数复杂性理论就是要对各种问题澄清是否存在这类算法。而我们的研究工作将会集中于：1。利用参数复杂性和经典复杂性间的同构关系来处理参数复杂性结构理论中的一些未解问题，特别是各种复杂性类的包含关系。2。考察许多组合问题是否存在参数或亚指数近似算法，同时发展相应的PCP理论。3。研究一种常见的设计参数可解算法的方法，即内核化技术，包括寻找许多组合问题的多项式内核算法或证明其不存在。