JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 3 4 5 ]    NEXT >
. | Reply
.
. (response to post by rsarge) | Reply
.
. (response to post by rsarge) | Reply
.
Re: Polynomial-time algorithm solving Graph Isomorphism problem, O(N^5) (response to post by rsarge) | Reply
First of all, research isn't about secrets. If you want anyone to take you seriously you need to clearly communicate your ideas rather than hide in mystery. Do you understand what the consequences of GI being in P are and aren't? What does your algorithm do that existing algorithms don't? How can you explain why this solution hasn't been arrived at before?

If you can't answer these questions you probably should be pretty skeptical about your work. For me looking at your algorithm it's pretty clear that it ignores most of the subtleties of the GI problem. Anyway, your algorithm fails to identify this isomorphism.

Edit: And while I'm at it let me say this algorithm doesn't even seem close to something that could work. A small modification is not going to save it.

11
 
0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0
 
0 1 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0
Re: Polynomial-time algorithm solving Graph Isomorphism problem, O(N^5) (response to post by rsarge) | Reply
You can put your code inside a [ c p p ][ / c p p ] section, it will keep the indentation and highlight your code, which will make it easier to read.
. (response to post by msg555) | Reply
.
Re: Polynomial-time algorithm solving Graph Isomorphism problem, O(N^5) (response to post by rsarge) | Reply
It seems the permutation is 6 7 8 9 10 0 1 2 3 4 5

BTW I'm not that opposed to secrecy. That's anyone's free choice. I think the anagrams thing people did yesteryear is fun too.
. (response to post by rsarge) | Reply
.
. (response to post by rsarge) | Reply
.
. (response to post by rsarge) | Reply
.
Re: Polynomial-time algorithm solving Graph Isomorphism problem, O(N^5) (response to post by rsarge) | Reply
Edit: Seems the case was not what I intended (though there is an isomorphism your algorithm does not detect apparently). Also seems you implemented bipartite matching.
. (response to post by msg555) | Reply
.
Re: Polynomial-time algorithm solving Graph Isomorphism problem, O(N^5) (response to post by rsarge) | Reply
I saw zero disrespect and hatred in msg555's post. He politely asked some of the questions you will hear (probably in a much less friendly form) as soon as you try to publish your results.

I see one more mistake in your last post. You consider posting test cases productive. In my opinion, looking for test cases and applying fixes is not productive at all.
The reason why I believe this: I do not believe that the algorithm can be fixed. You will just create more and more involved pieces of code, without any guarantee. And the added complexity will make it harder and harder for you to argue that your algorithm works.

"It works on all inputs I tried." is not a proof.
"It works on all inputs I and everyone else tried." is not a proof.
In general, the absence of a known counterexample is not a proof.

Graph isomorphism is an OLD problem. Many people tried. The best algorithms known so far are *far* from being polynomial. You are trying to bridge an enormous gap here. In order to succeed, you must be doing something fundamentally new that avoids all problems discovered in the past research. What is it?

Extraordinary claims require extraordinary evidence. And you should be the one providing the evidence.
Re: Polynomial-time algorithm solving Graph Isomorphism problem, O(N^5) (response to post by rsarge) | Reply
Well I don't mean to sound disrespectful. Just from my perspective (and everyone else's save perhaps yours) there is very little reason for me to believe your algorithm works. Moreover, having looked at your algorithm and seen what it does I have fairly high confidence it doesn't work and it's not a small modification from being there. Also the fact that I'm able to so easily come up with counter examples makes it look like you haven't put due consideration into the operation of your algorithm. Anyway as undirected cases seem tricky (though language wise I believe they are both GI complete) here's a small directed case to make up for the other one.

10
 
0 1 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 
0 0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
 
0 1 1 0 0 0 0 0 0 0 
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0


You probably can modify your code so this one works but that won't show anything. What your code reminds me of is Sudoku solvers. Sure you can always add in new heuristics to solve harder and harder problems but you'll probably never get them all in poly time unless something significant changes.
. (response to post by misof) | Reply
.
[ 1 2 3 4 5 ]    NEXT >

RSS