tag:blogger.com,1999:blog-3722233.post4197054057663794908..comments2020-05-25T04:05:03.716-04:00Comments on Computational Complexity: Flying Pigs Unsafe at Any SpeedLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-49488760745754790072019-03-02T08:39:36.033-05:002019-03-02T08:39:36.033-05:00... If P = NP we can solve AI! ...
That argument ...... If P = NP we can solve AI! ...<br /><br />That argument holds if you use AI for very "formal" applications. Even if you have an efficient NP algorithm for NP, to handle "natural" problems like speech recognition, language translation, OCR, ... you would end up doing things similar to what AI people do now.Majdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33333874150352161762019-03-02T08:30:02.388-05:002019-03-02T08:30:02.388-05:00... nearly all the known problems we know that sit...... nearly all the known problems we know that sit in polynomial time have practical efficient solutions ...<br /><br />That is arguable: For example, consider the (rightly) celebrated log-space algorithm of Omer Reingold for st-connectivity in undirected graphs. It has a polynomial runtime, O(n^c), but c >> 10^9.<br />see https://cstheory.stackexchange.com/questions/1063/time-complexity-analysis-for-reingolds-ust-conn-algorithmMajdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66166346432702382792019-03-02T08:02:37.905-05:002019-03-02T08:02:37.905-05:00What if AI can self-educate itself to solve TCS pr...What if AI can self-educate itself to solve TCS problems better than any theorist, in the same way that AlphaZero self-trained itselt to beat all chess masters and other chess programs?Majdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20637424868614930832019-03-01T11:00:07.059-05:002019-03-01T11:00:07.059-05:00Are theorists (specifically when wearing the compu...Are theorists (specifically when wearing the computational complexity hat) ever driven by real world applications? Algorithm theorists perhaps aspire for their algorithms to be used some day. <br /><br />I am not aware of any ideas and methods that hard core application oriented folks (especially with machine learning flavor) could bring to hard core theorists (and vice versa); perhaps I am being pessimistic. <br /><br />Machine learning folks are having their field day in the sunshine and are truly relishing it (perhaps also rubbing it in into others in different fields). <br /><br />I don't believe theorists ever had short term horizons for their science; their endeavors therefore cannot be quantified with a tangible easy-to-define (and verify) metric. The society has valued their work in the past and one hopes will continue to do so in the future despite the comings and goings of new technologies.space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69593383041416455102019-02-28T18:26:13.140-05:002019-02-28T18:26:13.140-05:00we can for all practical purposes solve NP-complet...we can for all practical purposes solve NP-complete problems -<br /><br />That can't really be true considering that the common encryption algorithms are effective in practice. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24137890261409236692019-02-28T09:46:58.819-05:002019-02-28T09:46:58.819-05:00Well his point seems to be $P\neq NP$ implies comp...Well his point seems to be $P\neq NP$ implies complexity theory may not be practical. If the whole point is to show $P$ not $NP$ then well what is the point of the problem?Anonymousnoreply@blogger.com