Timeline for Powerful Algorithms too complex to implement
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2017 at 20:10 | comment | added | user1271772 | -1 because the constant is "galactic" and the question went through exceptional effort to request NOT giving such an algorithm. | |
| Nov 30, 2011 at 23:44 | comment | added | Jeff Burdges | Isn't even compiling a single graph $H$ into the $O(n^3)$ algorithm to test for having $H$ as a minor an extremely difficult task? Hasn't the full algorithm only been implemented once or something? | |
| Jan 26, 2011 at 1:11 | comment | added | Aryabhata | @Suresh: I don't think the complexity is in question here. Whether the algorithm satisfies the question constraint of "could have practical value" is in doubt :-) | |
| Jan 25, 2011 at 0:40 | comment | added | Suresh Venkat | isn't it therefore "too complex to implement" ? :) | |
| Jan 24, 2011 at 18:21 | comment | added | András Salamon | The problem here seems deeper: there is no effective way known to generate the list of minors, so this doesn't actually yield an algorithm at all. Most minor-closed properties yield an infinite list of excluded minors, if one translates the logical expression directly. The Robertson-Seymour Theorem (Wagner's Conjecture) tells us that a finite list of excluded minors is lurking inside that infinite list, but the theorem gives absolutely no help in actually finding them. So Robertson-Seymour therefore usually leads to a pure existence proof. | |
| Jan 24, 2011 at 17:42 | comment | added | Lev Reyzin♦ | Interesting. Perhaps this should be added to the answer... | |
| Jan 24, 2011 at 15:00 | comment | added | Derrick Stolee | For instance, we don't even know the list of excluded minors for graphs embeddable in the torus. | |
| Jan 24, 2011 at 5:08 | comment | added | Suresh Venkat | The problem is the constant comes from the very large list of minors that one needs to exclude for a particular property. I don't know of any way to generate the desired list of excluded minors for a given property, so it's not just a scale issue . | |
| Jan 24, 2011 at 0:43 | comment | added | Aryabhata | Yes, this does not look like a good example. If I understand correctly, the question is about algorithms which could be practical (hence likely 'small' constants) but are just too complex to implement. Of course, the whole question is open to different interpretations :-) | |
| Jan 23, 2011 at 23:52 | comment | added | Lev Reyzin♦ | Is this also hard to implement or just has a huge constant? | |
| S Jan 23, 2011 at 9:26 | history | answered | Suresh Venkat | CC BY-SA 2.5 | |
| S Jan 23, 2011 at 9:26 | history | made wiki | Post Made Community Wiki |