tag:blogger.com,1999:blog-3722233.post114536221248177244..comments2023-09-28T12:45:24.391-05:00Comments on Computational Complexity: Favorite Theorems: Small SetsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-1145389002065522252006-04-18T14:36:00.000-05:002006-04-18T14:36:00.000-05:00Hmm... and I guess it's implausible that SAT is re...Hmm... and I guess it's implausible that SAT is reducible to a sparse set with log n queries, if and only if NP is contained in P/f(n) for some "small" f? (If we wanted a truly intermediate assumption, f would have to be bigger than logarithmic but smaller than polynomial.)Scotthttps://www.blogger.com/profile/12161309448306097395noreply@blogger.comtag: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