On Sat, May 03, 2025 at 01:17:34PM +0200, 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?
"Cardinality of set of topologies on [1,...,n]" is a simple formula, but somewhat inconvenitent one. There is also relatively simple formula in terms of number of T_0 topologies. > > 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 > > All these codes play out for n<=10, so one should identify the time/space > complexity of the algorithm: > > O(1) - Excellent/Best Impossible, O(1) algorithm can only give fixed number of answers. > O(log n) - Good Very unlikely to be useful, would need some funky compression scheme for answers. Of corses, writing "T(n)" (with explicit n) attains this complexity, but is useless. > O(n) - Fair > O(n log n) - Bad > O(n^2), That is the best possible with binary encoding of the result. > O(2^n) and O(n!) - Horrible/Worst Probably much better than any known method... -- Waldek Hebisch -- 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/aBYFWKfZQv_p9pVF%40fricas.org.
