tag:blogger.com,1999:blog-3722233.post1833386072149475494..comments2024-03-04T02:59:26.350-06:00Comments on Computational Complexity: 2007 Complexity Year in ReviewLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-53434770229863332822008-01-04T04:11:00.000-06:002008-01-04T04:11:00.000-06:00Happy new year indeed! In an article a few links ...Happy new year indeed! In an article a few links away you mentioned that for any k, the graph minor theorem implies the existence of an O(n**3) algorithm for determining whether a graph G has genus k. Do you happen to know if the converse is either 1) known to be true; or if not, then 2) has any hope of being true? That is, does the O(n**3) existence statement imply the graph minor theorem?<BR/><BR/>The idea of a nonconstrutive proof of existence of an O(n**3) algorithm is interesting. Has there been anything like that before?<BR/><BR/>Thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61504467260560663542008-01-01T19:26:00.000-06:002008-01-01T19:26:00.000-06:00happy new year~happy new year~Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89353383149841304522008-01-01T18:58:00.000-06:002008-01-01T18:58:00.000-06:00Happy new Year! ^_^Happy new Year! ^_^Anonymousnoreply@blogger.com