*A guest post by Jens Zumbraegel*I am working on cryptography, and I came across complexity theory only recently. My question is whether a general framework for the various types of reduction exists. Let me give motivation:

The concept of reduction in order to compare the computational hardness of algorithmic problems is a very important one. However many types of reductions are used in the literature for different purposes. Trying a rough classification:

- "Classical" complexity theory: Karp/many-to-one or Cook reductions
- Average-case complexity: Karp reductions with a domination condition between distributional problems
- Cryptography: "reducibility arguments" in "provable security", i.e. ad-hoc reductions of the problem BREAKING-THE-CRYPTOSYSTEM to some well-known hard number theoretic problem, like FACTORING

Back to my question - I wonder whether there is a general abstract theory of reductions, probably similar to category theory: One defines the class of algorithmic problems (the objects of the "category") and the type of reductions (the morphisms) one would like to consider. For example: (decision problems for languages in {0,1}

^{*}, Karp reductions). Such a general framework could help to set up a reduction theory for cryptography.Comments most welcome!

--

Posted By Lance to Computational Complexity at 8/06/2008 06:49:00 AM