Hi martin forwarding apparently worked ... On Sunday, 4 May 2025 at 11:30:59 UTC+2 Kurt Pagani wrote:
Hi Kurt, On 03/05/2025 12:17, Kurt Pagani wrote: > Hi Martin > > On 29/04/2025 18:25, Martin Baker wrote: >> This Wiki page says "There is no known simple formula to compute T(n) for arbitrary n" > > The "simple" is puzzling. I know no formula at all that could tell T(n) for arbitrary n. Do you? The Wiki page talks about a "simple formula" and some stackexchange posts talk about a "simple algorithm". I don't know if they are making a real distinction between "formula" and "algorithm" or if its just choice of words. I guess there are some numerical algorithms that can't be expressed as formulas? Can recursion be put in a formula? It's not so simple to define "simple" :-) I don't pay too much attention to this informal use of language, The semantics of 'formula' is manifold, e.g. in formal systems (à la Smullyan) you may describe things which you wouldn't call a formula in the ordinary sense, wheras what's "ordinary sense"? >> and forums like this: >> https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements >> seem to suggest that an efficient algorithm is an open problem. > > What's the meaning of "efficient"? > > https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n As far as I can tell these example all use what I call a brute-force method, that is, powerset of powerset and filter out valid topologies (I can't be sure because the aim seems to be to make the code as small as possible rather than understandable). That's true, however, I didn't find any other on the fly. What I would like is a way to define "efficient" which depends only on the algorithm and not the low level details of the language. For instance I think it should penalise algorithms which generate invalid results and then have to filter them out. > All these codes play out for n<=10, so one should identify the time/ space complexity of the algorithm: > > O(1) - Excellent/Best > O(log n) - Good > O(n) - Fair > O(n log n) - Bad > O(n^2), O(2^n) and O(n!) - Horrible/Worst I just see that I forgot providing the ref for the above: https://www.bigocheatsheet.com/ or https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/ I have no clear idea what O(?) we could expect at best. I was rather surprised that the step from n=5 to n=6 in your code has such an impact. The asymptotics, however, log_2(T(n)) ~ n^2/4 doesn't bode well, IMO. I will look at the references you gave. At first sight this looks like the theory around the 'P versus NP problem'. I think one of the classic problems is factoring multiplication of numbers whereas this problem is about factoring union/join of sets. So they are both about factoring so it would not surprise me if they had the same level of complexity. Very true! >> So what am I missing here? Why do they say its so difficult? > It seems to be difficult for n > 10 ... Do you know what the issue with n > 10 is? Is it just because the numbers are so large, or does something change such as a breakdown in symmetries? I have no clue, however, if the bounds 2^n <= T(n) <= 2^(n*(n-1)) are correct (I guess so), then, according to the asymptotics mentioned above, the numbers get very large indeed. Thank you very much for all these ideas, I will followup on the links and let you know how I get on. Martin -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/3703e186-b327-418a-865d-1bf7e149255bn%40googlegroups.com.
