last day (16 days later) » 

5:02 PM
-2
Q: An algorithm for graph isomorphism

jim198810I have an idea for a Graph Isomorphism algorithm with complexity $$(n^{log_2(n) }/2^{\sum k})^{s}$$ where $k \cdot s = n$ is the number of vertices of the input graphs. I am not sure, it is likely to be wrong. I have written a PPT document(demonstration) and a pseudo-code. Can I share the idea? ...

 
It is not usually considered appropriate here to ask only for the checking of correctness. What you might ask is whether what you have done is credible. Graph isomorphism is likely to be a well analyzed problem. So improving its complexity is probably a big claim. You could start by asking whether the complexity you claim is actually achievable. If you get a competent negative answer, you may then ask what is wrong with your proposed algorithm. Well, that is one way to do it. We all run a some point into the (too often) belief that we may have solved a hard problem.
Please, can you define explicitly $n$, $s$, and $k$. It may be standard, but standards may vary :).
 
@Raphael, I am not sure, it is likely to be wrong, but it seems a good idea to me, i just want to get some feedback from SE, not a confirmation.
anything else than arXiv ??
 
We do not mean to distrust you, but it is good prctice in reasearch to be very defensive with new extraordinary result. The author himself has to take the position of finding out why it could be wrong. It is hard to advise you as you give no information about yourself or your environment, or about the general content of what you have done. Do you have a mathematical proof of correctness of your algorithm? If not, what reason do you have to believe your algorithm is correct?
 
@babou please, feel free to distrust!! I would like to know what other people think about the idea .I am an undergrad student, i am going to share a link to the ppt, I think it would be better to have a look at it. i will provide a pseudo-code later if any one asks. problem is , people in SE are quite "uptight", my question is put on hold already!!
@Juho, tried my department already ;) , they have not found any thing wrong, at the same time they have not confirmed it!! is there any other site i can share??
@Juho , Its just the idea, not the proof!!
So, I need to delete this post( down vote might restrict me to ask question in future)??
 
No. Downvote will not do anything if you do not have reputation points to loose. You might get restricted if you ask too many silly question. But this is the only one. The point of people reaction is that many people have ideas, but that is far from enough, especially on a hard problem. Ideas from a seasonned scientist might get some consideration, because he would be trusted to be unlikely to make trivial mistakes, and would be known to be aware of all the know pitfalls and dead tracks,. But you are not in this situation, and ideas from a beginners are much more likely not to work.
You cannot expect very busy people to invest time on just an idea that, from our social experience of science, is unlikely to work. You have to do the job of provioding a proof, if only to prove you understand your technique well enough to describe it formally. Examples are unlikely to convince anyone.These are the rules of the game because it is the best we know we can afford. Research scientist spend a lot of time checking each other's work. They do not have enough of that time. So they have to use it sparingliy.
 
5:02 PM
well , I am not expecting anyone to confirm my Idea, it was informally written so it becomes easier to understand within minimal time, if I wrote it formally it would take much time to get an overview than the PPT I gave. Anyway, I knew this kind of question might not be welcome here(you know, as you have followed this post from the outset ) . Another fact is , the example was used to explain, if you understand the idea , you would see it would work for any kind of graph. I have not proposed anything based on one example :). can I post it here if I write the whole thing formally??
I am sure that the algorithm would work, the issue is the complexity I claim. If anyone understand the PPT, he can use the same procedure for any other graphs. Question might arise about irregular graph, well, in that case , it is less time consuming since irregular graph/matrix is easy to partition.
 
Your question was put on hold to keep some order. This may be reversed. You are free to edit it as you see fit as long as it is in good faith. Downvote can hurt only your feelings. Believe me, it is not as bad as being donwvoted by a journal after working hard for months or years on a difficult issue, which happens to many of us,including some reputed scientists. Actually, everyone has been rather kind, believeme.
 
@babou :) thanks for your comments, you have been kind to me from the beginning. Anyway , have read the PPT(just curious)??
 
 
2 hours later…
7:29 PM
@jim198810 I read the new version of your post, though not in much detail. I did not read the PPT, and I will not, for a very good reason: I have no competence on this topic. Even if I were able to red you and understand, my opinion would be worthless.
I read your initial contribution because I occasionally read contributions of new users to do some sanity check on style, topicality and other general qualities of contributions, so that the site does not get cluttered with all kinds of irrelevancies. For example, we have to weed out many questions about programming which are off topic.
 
understood :)
 
My best advice, if you can afford the time, is for you to work on the proof. It is good training. If you succeed ... great (do not set your hope too high). If you fail, you may learn a lot from it. But do not do it at the expense of your normal training.
And do not believe that anyone is against you for bad reasons. All scientists are eager to learn new stuff, to get the answer to open problems.
 

  last day (16 days later) »