tag:blogger.com,1999:blog-3722233.post6014323808827607068..comments2020-08-06T15:50:18.033-04:00Comments on Computational Complexity: A Theory of Reductions?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-56239282984684429282008-08-07T06:50:00.000-04:002008-08-07T06:50:00.000-04:00Thanks - you two pointed me to interesting work......Thanks - you two pointed me to interesting work...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84850610007901815582008-08-06T11:26:00.000-04:002008-08-06T11:26:00.000-04:00Why do you refer to the "reducibility arguments" i...Why do you refer to the "reducibility arguments" in "provable security" as "ad-hoc"? It sounds like you are unaware of the way cryptographic proofs of security work; you might want to see the Katz-Lindell textbook for a good introduction to these topics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60421838251214818932008-08-06T10:33:00.000-04:002008-08-06T10:33:00.000-04:00A paper which addresses this topic is "Notions of ...A paper which addresses this topic is "Notions of Reducibility between Cryptographic Primitives" by Omer Reingold, Luca Trevisan and Salil Vadhan (TCC 2004).<BR/><BR/>Hope this helps.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35717574546491585662008-08-06T10:05:00.000-04:002008-08-06T10:05:00.000-04:00With only problems and reductions, you're not ...With only problems and reductions, you're not going to get much more than new terms for complexity concepts. For example:<BR/><BR/>Category theory <-> Complexity theory<BR/>objects <-> NP problems<BR/>morphisms <-> poly-time many-one reductions<BR/>initial objects <-> problems in P<BR/>final objects <-> NP-complete problems<BR/>direct sums <-> tagged unions<BR/>...Anonymousnoreply@blogger.com