Re: Combinatorics of binary operations

On Sat, 14 Apr 2007 13:39:24 -0400, "Stephen J. Herschkorn"
<sjherschko@xxxxxxxxxxxx> wrote:

It is easy to see that there are n^[n (n+1) / 2] distinct commutative
binary operations on a set with cardinality n. How many distinct
nonisomorphic such structures are there? How many associative binary
operations are there? Nonisomorphic associative operations?

Are these "hard" questions?

No references, but yes, I'm certain they are hard.

In fact, even deciding whether two such structures are isomorphic is
not (not yet, anyway) algorithmically decidable in polynomial time.
Any such algorithm would give, as a special case, an algorithm for
graph isomorphism.

quasi
.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Since graph isomorphism is a long studied problem with (AFAIK) no known ... my algorithm is more than likely flawed. ... this is a randomized algorithm that has a probability of failing (that is, ...
    (sci.crypt)
  • Re: Algorithm to determine matrix similarity
    ... such an S would be an algorithm to decide whether ... The OP's problem subsumes the graph isomorphism ... 2-colored undirected graphs (with self-edges). ... matrices amounts to classifying the nodes by ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... to do the sorts of things that have been stated ... "Is graph isomorphism in P?"... ... whether the algorithm works or not. ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... Bill Cox wrote: ... significant progress analyzing this algorithm. ... Since graph isomorphism is a long studied problem with no known ...
    (comp.theory)
  • Re: Combinatorics of binary operations
    ... binary operations on a set with cardinality n. ... Perhaps you might look in the OEIS for entries related to groupoids or ... semigroups. ...
    (sci.math)
Loading