tag:blogger.com,1999:blog-3722233.post3299749567675625592..comments2022-12-07T07:34:35.444-06:00Comments on Computational Complexity: The Structure of Data and Machine LearningLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-85707663158775742222022-11-12T10:32:11.107-06:002022-11-12T10:32:11.107-06:00If I understand it correctly, Lance means for one ...If I understand it correctly, Lance means for one thing the following: <br />Many optimization problems are NP hard. Since the methods of ML (or some other extensions of ML) can be used to efficiently find solutions to these problems which are near optimal, or practically sufficiently optimal, it seems that P=NP is practically holds or practically credible rather than incredible. <br />To emphasize, it is so regardless of whether P=NP is used as assumption.<br /><br />This puzzling phenomena might be explained without having to alter our beliefs about P vs NP.<br /><br />In theory of computation, exact optimal solutions to NPC or NP hard optimization problems may not be in P; but practically optimal solutions to these problems may be in P (depending on how 'optimal' is meant)<br />And there may be gaps of infinity between the practically optimal and the exact optimal.<br />Also important to note is that for many practical optimization problems, it is difficult if possible to define what are their exact solutions.<br /><br />By analogy, in physics, we are told that it is impossible for particles with nonzero static mass to be accelerated to the speed of light because infinite amount of energy is needed to achieve this; but it is possible for those particles to be accelerated near the speed of light.<br />computationalisthttps://www.blogger.com/profile/13876886980860698327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13378404374721990932022-11-11T11:25:20.412-06:002022-11-11T11:25:20.412-06:00Fixed. Thanks.Fixed. Thanks.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59139260211252749902022-11-11T11:24:06.683-06:002022-11-11T11:24:06.683-06:00log(S) should be log(|S|)?log(S) should be log(|S|)?Anonymousnoreply@blogger.com