Speaker:

Mingyu Xiao(University of Electronic Science and Technology of China)

Host

Institute for Interdisciplinary Information Sciences, Tsinghua University

Time:

2021-03-22 16:00-2021-03-22 17:00

Address:

Tsinghua University FIT1-222

Abstract:

Under the hypothesis P != 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.