tag:blogger.com,1999:blog-3722233.post7683685420037306979..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: The Structure (or lack thereof) of DataLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-41377632756727655412010-05-28T22:52:34.249-04:002010-05-28T22:52:34.249-04:00Anonymous: there are all sorts of such restricted ...Anonymous: there are all sorts of such restricted models. For example, the model of communication complexity provides such a model. Assuming only oracle access to the input, where the oracle captures the intuitively interesting questions about the input, one can often show unconditional lowerbounds. For example, the problem of maximizing a submodular set function subject to a matroid constraint, using only value oracle access, can be shown to be unconditionally hard. There are many other examples, I believe.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60098246652639405222010-05-28T16:03:16.422-04:002010-05-28T16:03:16.422-04:00A partial step would be to considered reasonable r...A partial step would be to considered reasonable restricted models. This would alone will be interesting, e.g. if we have a good model capturing the intuitive notion of a dynamic algorithm and prove that it can not solve SAT in polytime, I would consider it an interesting partial step. These kind of results would show that some ingenuity is required in designing an algorithm (if there is one) for SAT, and would make it much easier to reject the claims from people with an algorithm showing P=NP.<br /><br />Would not these ML algorithms to be related to BPP rather than P?Anonymousnoreply@blogger.com