论文标题
数据库理论和约束满意度中的现代下限技术
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
论文作者
论文摘要
有条件的下限基于$ p \ neq np $，指数时间假设（ETH）或类似的复杂性假设可以提供有关可能可以使用哪种类型的算法的非常有用的信息。理想情况下，这样的下限将能够证明最著名的算法基本上是最佳的，并且无法进一步改进。在本教程中，我们概述了不同类型的下限，并查看如何将它们应用于数据库理论和约束满意度中的问题。
Conditional lower bounds based on $P\neq NP$, the Exponential-Time Hypothesis (ETH), or similar complexity assumptions can provide very useful information about what type of algorithms are likely to be possible. Ideally, such lower bounds would be able to demonstrate that the best known algorithms are essentially optimal and cannot be improved further. In this tutorial, we overview different types of lower bounds, and see how they can be applied to problems in database theory and constraint satisfaction.
