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?
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
O(log n) - Good
O(n) - Fair
O(n log n) - Bad
O(n^2), O(2^n) and O(n!) - Horrible/Worst
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.
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/91f7d025-6af6-437b-b289-a1da7cad2fd5%40martinb.com.
