Is this solution to an open conundrum correct?

Question

I believe that I have solved an open problem in complexity theory but I want to make sure that it's right.

I problem in question is: ``How many moves does it take to solve the Towers of Hanoi puzzle as the number of towers increases?''

What is obvious is that if the number of ''disks'' is kept bounded, then then running time asymptotically approaches O(n) where n is the number of ''disks''. This is significantly better than the original O(2^n).

What I've found is that the running time is O(2^n^(1/k)) where n is the number of disks, k is the number of pegs, and exponentiation (the ^ operator) is right associative. Although, this comes about because of a weird phenomena where there are discrete points where the running time increases linearly and then changes slope. So all in all, the running time amortized O(2^n^(1/k)).

If you're curious about it and want to read the proof for yourself, I set up a website where you can find it over here. (If that link is inaccessable, try github. Although you'll need access to the necessary tools to build it)

Because I know that someone is going to ask me ''Why don't I just give it to my professor?'' or something else along those lines. The answer is that I'm not affiliated with any university/college, I'm still in high school.

Any help is very appreciated, thank you in advance.

Notice: This question has been re-posted on Math Overflow over here

Notice: When the recomended formatting edits are made to the paper, another bounty will be issued on a new question that will be posted as I am looking for criticsm on the content of the paper rather than the legibility of it.

Answer 1

I did try to look pretty in-depth at the article, and found it very confusing and hard to read in the same way as @sth. I have an academic background so am used to reading (often poorly written) papers, but found this one pretty hard to go through.

I don't want to dishearten you but you should have someone go through and help you re-write it if you want to reach any significant audience.

Claimed proofs of or counterexamples to famous outstanding conjectures appear every day (look around http://arxiv.org, I bet P vs. NP has been solved at least once this week), and are often discredited out of hand if all three of the following things do not hold:

• the author is already established and has a good reputation for being correct and careful,
• the paper clearly has a significant, new idea, rather than apparently mysteriously extracting a proof from unmotivated symbolic manipulation (if it were possible, one of the many smart, experienced people who have worked on the problem, or a computer, would likely have found such a solution),
• the paper explains clearly what the roadblocks were to finding a solution, and how this new idea overcomes it.
• It helps if the paper is well-written, but a poorly-written paper satisfying the above will still get some attention.

Probably over 99% of claimed solutions to famous open problems are wrong, and papers that fail a 60 second smell test are most often thrown away by people who are actually equipped to evaluate them.

Sorry to say, you meet none of the above criteria. This doesn't mean that your proof is wrong, but it does mean that people who are able to evaluate it will be reluctant to spent the necessary time, particularly because the paper is hard to read. Never mind that it is not actually clear what you are claiming to have proved.

Some specific complaints:

• I don't see anywhere a description of an actual algorithm. If you claim to have achieved a certain time complexity improvement, you should either include an algorithm attaining it or explain why your proof cannot be adapted to be constructive.
• You nowhere clearly describe the approaches people have attempted to solve the problem, and how your approach is similar to or different from theirs.
• You don't state your significant new idea that solved this problem. The proof appears to use nothing beyond basic arithmetic. Sorry, I love down-to-earth concrete math, but I guarantee that everyone who has ever worked on this problem has a solid command of arithmetic, and if no other tools are necessary to attain a 4-page solution then probably someone would have found it by now.
• I had hoped to find an implementation of an algorithm attaining your claimed time complexity (never mind that I am not clear on what the claim is) in the Python file you attach. However, to my dismay, the script apparently just runs a computation of the closed-form expression that you provide in your paper.

I expect some people will come to your "defense" (despite that this is not an attack, but honest advice), because you are a high-schooler and this is "amazing" for a high-schooler. Right now there are two posts already in this spirit, and neither author seems to even know what you are claiming to prove.

I recommend you clean the paper up as best you can and post it on Math or CS StackExchange (Edit: apparently Math StackExchange has a ban on posting "solutions" to open problems, probably for the reasons I describe above!), where there will be a much larger audience that is equipped to look at it and evaluate it carefully. I recommend you also look for other articles on the same topic (there are certainly dozens if not hundreds), look up the authors of those articles, pick one who is relatively junior (a full professor will be harder to convince to interact with you), and send him what you have personally to see what he thinks. I would avoid emphasizing that you are in high school, as in my experience, most academics will not be impressed and will be much more ready to write you off as a likely waste of time.

@mrip has some nice references and advice for you as well. Good luck.

Edit: Just for fun, here are two claimed solutions to P vs. NP from this last summer, and an article that explores the anthropological side of P vs. NP:

• http://arxiv.org/abs/1304.1307 Quote from abstract: "First of all, we prove P != NP..."
• http://arxiv.org/abs/1305.4029
• http://arxiv.org/abs/0904.3074

Edit for record-keeping: The article linked at http://arxiv.org/abs/1112.0631 is a paper claiming to prove the same thing as you (maybe), so it's a great first place to look and first person to contact.