tag:blogger.com,1999:blog-3722233.post1110572478221348469..comments2017-04-28T10:57:44.459-04:00Comments on Computational Complexity: Understanding Machine LearningLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-86856284534739945162017-04-27T11:54:31.804-04:002017-04-27T11:54:31.804-04:00I will remove the link http://vixra.org/pdf/1704.0...I will remove the link http://vixra.org/pdf/1704.0335v1.pdf and use instead:<br /><br />https://hal.archives-ouvertes.fr/hal-01509423/documentFrank Vegahttp://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11362389673777786662017-04-25T13:02:51.140-04:002017-04-25T13:02:51.140-04:00Given a number x and a set S of n positive integer...Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.<br /><br />You could read the details in:<br /><br />http://vixra.org/pdf/1704.0335v1.pdfFrank Vegahttp://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42566041749722530362017-04-18T10:00:14.982-04:002017-04-18T10:00:14.982-04:00To your list of reasons to care, I would add anoth...To your list of reasons to care, I would add another: that the problem of understanding which learning tasks are feasible for these methods is a fascinating and important one from a purely intellectual point of view.gowershttp://www.blogger.com/profile/11312457281302462824noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75958213356228022182017-04-17T17:31:35.392-04:002017-04-17T17:31:35.392-04:00If P=NP you could also find the shortest proof in ...If P=NP you could also find the shortest proof in your favorite formal system that the smallest possible circuit does what you wanted it to do, as well as any other claim you are wondering that may be true about the circuit. That proof might not be comprehensible to you, but it could be written in a format where proof assistant software such as HOL or Coq could parse it and convince you it is correct. So if P=NP (with feasible low constants) I think that would definitely help.ryanwhttp://www.blogger.com/profile/09644595632189419277noreply@blogger.com