tag:blogger.com,1999:blog-3722233.post4130341426674002552..comments2024-08-06T04:49:57.910-05:00Comments on Computational Complexity: Graph Minor Theorem and Non Const AlgorithmsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-17617426493440610872008-01-07T10:51:00.000-06:002008-01-07T10:51:00.000-06:00Commenter 9 is correct,so the question should beAr...Commenter 9 is correct,<BR/>so the question should be<BR/><BR/>Are there OTHER (poly time)<BR/>algorithms for problems of<BR/>interest where the proof<BR/>that the algorithm works,<BR/>OR the proof that it terminates<BR/>in poly time, is nonconstructive.<BR/><BR/>bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33722627810519891622008-01-07T09:28:00.000-06:002008-01-07T09:28:00.000-06:00What Gasarch is talking about is cases in which yo...<I>What Gasarch is talking about is cases in which you can prove that an algorithm exists but the proof does not actually tell you an algorithm.</I><BR/><BR/>Then, from my understanding, an unambiguous way to describe this would be 'nonconstructive proof of existence of an algorithm' since it is the <B>proof</B> which does not supply a construction.<BR/><BR/>The word 'nonconstructive' is an adjective that, in my usage, means what it modifies does not construct something.<BR/><BR/>Therefore 'nonconstructive algorithm' would be an algorithm that does not construct something. Further 'nonconstructive proof' would be a proof which does not construct something.<BR/><BR/>In this case the proof does not construct, but proves the existence of, an algorithm. Hence it is a 'nonconstructive proof', but I do not think the algorithm proven to exist should be called 'nonconstructive' (unless it is also a 'nonconstructive proof' as in the primality testing example).<BR/><BR/>The example I gave is in fact a 'nonconstructive proof', but since the proof is an algorithm I think the term 'nonconstructive' <B>could</B> be applied. Should it? I think this discussion indicates that it is probably safer to stick with the term 'nonconstructive proof' in which case BG's query (as I currently understand it) becomes "Do there exist more nonconstructive proofs which prove the existence of an algorithm?"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40430265351146764922008-01-06T17:44:00.000-06:002008-01-06T17:44:00.000-06:00This comment has been removed by a blog administrator.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71167990863546357602008-01-06T17:16:00.000-06:002008-01-06T17:16:00.000-06:00I don't think "non-constructive algorithm" is an i...I don't think "non-constructive algorithm" is an instantly recognizable, universal technical term, but I've heard it before.<BR/><BR/>Primality testing is not an example in the sense of this posting. What Gasarch is talking about is cases in which you can prove that an algorithm exists but the proof does not actually tell you an algorithm.<BR/><BR/>This is what happens with the graph minor theorem. Given any minor-closed family of graphs, there is always an algorithm for testing membership. Specifically, the family is characterized by a finite set of excluded minors, and you just need to check for them. However, the proof of the theorem gives no method for actually writing down the excluded minors, and without that this method doesn't lead to an actual algorithm, even though it proves that an algorithm definitely exists.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45810143770972590402008-01-06T09:35:00.000-06:002008-01-06T09:35:00.000-06:00I think the term 'nonconstructive algorithm' makes...I think the term 'nonconstructive algorithm' makes a lot of sense.<BR/><BR/>Consider primality testing algorithms.<BR/><BR/>Any currently known fast primality testing algorithm could be considered 'nonconstructive' because in certain cases when they return that a number is composite it proves that there is a factor of the input, but it doesn't tell you what it is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81562666304242581752008-01-05T19:23:00.000-06:002008-01-05T19:23:00.000-06:00The oxymoronic phrase "nonconstructive algorithm" ...The oxymoronic phrase "nonconstructive algorithm" sounds like a <A HREF="http://www.yogiberra.com/yogi-isms.html" REL="nofollow">Yogi-ism</A>. Is that expression actually used in the literature, or is it just blogging shorthand for something longer which, while more technically correct, doesn't exactly roll off the tongue (in which case maybe we should call "nonconstructive algorithm" a Gasarch-ism)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46742789839459005002008-01-05T05:09:00.000-06:002008-01-05T05:09:00.000-06:00Corrections in previous post,For a fixed graph H, ...Corrections in previous post,<BR/><BR/>For a fixed graph H, give a polytime algorithm which given an edge-weighted graph G returns the minimum weight subgraph that contains a minor of H.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52410285984020214872008-01-05T05:06:00.000-06:002008-01-05T05:06:00.000-06:00Does the following problems also follows from GMT:...Does the following problems also follows from GMT:<BR/><BR/> For a fixed graph H, give a polytime algorithm which given an edge-weighted graph G returns the minimum weight minor of H.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62716032678700824192008-01-05T03:18:00.000-06:002008-01-05T03:18:00.000-06:00A side effect of Mohar's algorithm is a constructi...<I>A side effect of Mohar's algorithm is a constructive proof of Robertson and Seymour's theorem that genus-g graphs have a finite number of forbidden minors.</I><BR/><BR/>Presumably this doesn't actually give an effective way of generating the list of forbidden minors, since such a list is unknown even for g=1.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38750758165982599892008-01-04T18:09:00.000-06:002008-01-04T18:09:00.000-06:00Bojan Mohar describes an algorithm to determine wh...Bojan Mohar describes an algorithm to determine whether a graph as genus at most g in f(g)*O(n) time [STOC 1996, SIAM Discrete Math 1999]. The algorithm either constructs an embedding or finds a forbidden subgraph. I believe the dependence on g is doubly-exponential. (The graph-genus problem is NP-hard [Thomassen 1989], so exponential in g is the best one can hope for.) A side effect of Mohar's algorithm is a constructive proof of Robertson and Seymour's theorem that genus-g graphs have a finite number of forbidden minors.<BR/><BR/>See also Kawarabayashi and Reed's STOC 2007 paper. They describe an algorithm to determine in f(k)*O(n) time whether a graph can be drawn in the plane with at most k crossings.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.com