The art of reduction
Abstract
Everyone is familiar with NP-completeness, and the basic idea that appropriate reductions can tie together seemingly unrelated computational problems. The last couple of decades have seen an incredible growth and sophistication in utilizing reductions and completeness. These tie together seemingly unrelated computational notions, models and even whole subareas of computer science. I will survey such results, and their general and diverse consequences.