How fast can we solve NP-complete problems?
- Speaker
- Mingyu Xiao
- Affiliation
- University of Electronic Science and Technology of China
- Date
- Time
- – Asia/Shanghai
- Venue
- Tsinghua University FIT1-222
Abstract
Under the hypothesis $P \ne NP$, NP-complete problems cannot be solved in polynomial time. Under ETH, the SAT problem (the first NP-complete problem) cannot be solved in sub-exponential time. Under SETH, the SAT problem has not algorithms with running time better than the trivial bound $O(2^n)$, where $n$ is the number of variables in the formula. However, there are some NP-complete problems that allow algorithms with running time bound much better than the trivial bound $O(2^n)$, and some NP-complete problems that can be solved in sub-exponential time even when ETH holds. In this talk, we will introduce some techniques to design algorithms breaking the border of $O(2^n)$ and also to design sub-exponential algorithms.
Host
Institute for Interdisciplinary Information Sciences, Tsinghua University