tag:blogger.com,1999:blog-3722233.post114536221248177244..comments2024-08-02T16:56:41.757-05:00Comments on Computational Complexity: Favorite Theorems: Small SetsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-1145384462433968652006-04-18T13:21:00.000-05:002006-04-18T13:21:00.000-05:00Lance's last question is more natural than it may ...Lance's last question is more natural than it may look. SAT has a reduction to a sparse set with poly(n) queries if and only if NP has polynomial size circuits (think about it for a minute, if you have not seen the proof before), and (as explained in the post) a reduction with O(1) queries iff P=NP. So the case of log n queries is a quite interesting "intermediate" case between a uniform and a non-uniform assumption.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.com