Scheme-Theoretic Approach to Computational Complexity. III. SETH
Ali Çivril
所有作者
Ali Çivril
文献摘要
We show that there exist infinitely many n∈Z+ such that for any constant ε>0, any deterministic algorithm to solve k-SAT for k≥3 must perform at least (2k−23−ε)k+1n operations, where n is the number of variables in the k-SAT instance.