tag:blogger.com,1999:blog-3722233.post114354847131373237..comments2020-01-23T21:34:59.362-05:00Comments on Computational Complexity: Science Without BordersLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-1144243727355086372006-04-05T09:28:00.000-04:002006-04-05T09:28:00.000-04:00I've heard it suggested that we should try to keep...I've heard it suggested that we should try to keep doing math in different languages as it gives somewhat different perspectives for looking at something. However, most people I've seen advocating this position are native French speakers...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143648657951366752006-03-29T11:10:00.000-05:002006-03-29T11:10:00.000-05:00We should find P versus NP in logic view actually ...We should find P versus NP in logic view actually my friend and I have already been learning first order logic and second order logic--another beautiful science.<BR/><BR/>Computer theory Scientist have already proved some relationship between P, NP and second logic.<BR/>And we believe we can go further.caishenghttps://www.blogger.com/profile/08783192659827265607noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143599282970927652006-03-28T21:28:00.000-05:002006-03-28T21:28:00.000-05:00In Theory has all the makings of a fabulous blog!C...In Theory has all the makings of a fabulous blog!<BR/><BR/>Check out the <A HREF="http://in-theory.blogspot.com/2006/03/censors-with-idiosyncratic-taste.html" REL="nofollow">latest entry</A> for an amusing take on the internetionalization from the other side of the Great Wall...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143596481594095262006-03-28T20:41:00.000-05:002006-03-28T20:41:00.000-05:00Maybe the worst thing about the P vs NP question o...Maybe the worst thing about the P vs NP question on slashdot is that the meaningless answer "undecidable" is included in the list (let alone the fact that it is currently winning).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143596336066009592006-03-28T20:38:00.000-05:002006-03-28T20:38:00.000-05:00it's not so strange that people get the definition...<I>it's not so strange that people get the definition of NP wrong; "non-polynomial" is much more natural as a first guess than "non-deterministic polynomial,"</I><BR/><BR/>The acronym NP is just the worst possible name some could come up with to describe "Non-deterministic Polynomial" when P is defined as "Polynomial". At the very least, it should be P vs NDP if not something else.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143594559786173122006-03-28T20:09:00.000-05:002006-03-28T20:09:00.000-05:00I might be better to call it P vs PV. Polynomial v...I might be better to call it P vs PV. Polynomial versus polynomially verified. Verifiers are a much more useful concept today than when Sipser's book was being written, and it helps to understand the newer techniques.<BR/><BR/>As for borders, just look back to the Cook Levin Theorem. Many today seem to call it "Cook", but Levin's results behind the iron curtain show how much is wasted if we are separated from communication.<BR/><BR/>To really remove the borders, all scientific research should be done in English, so more obscure results won't be missed. (I agree that any single language would be good... but English is the only language in use today that can be expressed in 7-bit ASCII, so there's that. And yes, I'm being sarcastic in that there are much better reasons to pick English anyway.)Macneilhttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143582769143105522006-03-28T16:52:00.000-05:002006-03-28T16:52:00.000-05:00Should we change the name ofNP to NDP so thatpeopl...Should we change the name of<BR/>NP to NDP so that<BR/>people cannot easily<BR/>take it as <BR/>non-polynomial?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143579138602583812006-03-28T15:52:00.000-05:002006-03-28T15:52:00.000-05:00it's not so strange that people get the definition...it's not so strange that people get the definition of NP wrong; "non-polynomial" is much more natural as a first guess than "non-deterministic polynomial," I suppose. the weird thing is that they don't immediately conclude that P=NP is tautologically false. this post in particular goes on to say that if P does equal NP, then the world would change... (disappointingly, he doesn't mention that I will be the new pope.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143575305775702642006-03-28T14:48:00.000-05:002006-03-28T14:48:00.000-05:00The comments to the P=NP poll are much more sad th...The comments to the P=NP poll are much more sad than hilarious. Someone decided to "explain" what P and NP are and wrote: "NP stands for the set of problems that can't be solved in polynomial time. These problems take an exponential amount of time to solve, so usually can't be solved within a reasonable amount of time by a computer." I wonder what is it about this problem that makes it so hard for people to understand correctly?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143559844752489172006-03-28T10:30:00.000-05:002006-03-28T10:30:00.000-05:00Great point. The best thing (at least for me) is ...Great point. The best thing (at least for me) is the internationalization of the internet.<BR/><BR/> <A HREF="http://chinalawblog.com/" REL="nofollow">China Law</A>China Law Bloghttp://www.chinalawblog.comnoreply@blogger.com