Re: Is graph isomorphism in P?

On Jul 21, 5:36 pm, Fra <fra.cristi...@xxxxxxxxx> wrote:
On 21 Lug, 20:46, riderofgiraffes <mathforum.org...@xxxxxxxxxxxxxx>
wrote:

Fra - what you have done may have been difficult,
and may be useful, but you are not proving that
Graph Isomorphism is in P. To do that you need
to do the sorts of things that have been stated
earlier.

I never states that showing solutions for hard
Matrix Isomorphism problem is a proof that GI
is in P. I meant that, find isomorphisms for
hard istances of MI problem, for which are
not knew polinomial-time algorithms, should be
taken as a significant result.

Perhaps I've made a mistake calling this post:
"Is graph isomorphism in P?"... please excuse me
for this misunderstanding.

Another thing that is important is that last week, I responded to
another thread, from someone who claims to have proven that graph
isomorphism is in P. If you check that thread, you'll find a
description of the algorithm, and there I am able to say more about
whether the algorithm works or not. Otherwise, like I've said before,
I'm only "taking shots in the dark".

Your reply is basically saying that these things
are too hard, and you can't see how to do them.

Sorry I don't understand this, what is "too hard to do"?
If you can't see the website on which I've placed
algorithm's results, well this problem is derived
by a maintenance problem of the hosting service.
If you allude to the absence of any algorithm's
description, correctness proof and its study of
complexity, well, once a time, in this phase
I'm testing the algorithm and its implementation
in java, and I've invited all people involved in
the GI problem to give me hard instances of it,
no more no less.

This is excusible if (and it appears to be the case that) there are no
websites devoted to the Graph Isomorphism problem, as there are for
other areas of mathematics.

--- Christopher Heckman

.

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: (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. ... Any such algorithm would give, as a special case, an algorithm for ... graph isomorphism. ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... not knew polinomial-time algorithms, should be ... "Is graph isomorphism in P?"... ... the GI problem to give me hard istances of it, ...
    (sci.math)
Loading