Mathematics of the impossible: Computational Complexity, chapter 4, reductions
Thoughts 2023-02-09
Summary:
All posts in this series. A PDF version of this post will be published with a delay, but if you’d like to have it soon let me know. Contents 4 Reductions 4.1 Types of reductions 4.2 Reductions 4.2.1 Multiplication 4.2.2 3Sum 4.3 Reductions from 3Sat 4.4 Power hardness from SETH 4.5 Search problems 4.5.1 Fastest […]