StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIs this solution to an open conundrum correct?
text
Body
copied!<p>I believe that I have solved an open problem in complexity theory but I want to make sure that it's right.</p> <p>I problem in question is: ``How many moves does it take to solve the Towers of Hanoi puzzle as the number of towers increases?''</p> <p>What is obvious is that if the number of ''disks'' is kept bounded, then then running time asymptotically approaches <code>O(n)</code> where n is the number of ''disks''. This is significantly better than the original <code>O(2^n)</code>.</p> <p>What I've found is that the running time is <code>O(2^n^(1/k))</code> where <code>n</code> is the number of disks, <code>k</code> is the number of pegs, and exponentiation (the <code>^</code> 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 <em>amortized</em> <code>O(2^n^(1/k))</code>.</p> <p>If you're curious about it and want to read the proof for yourself, I set up a website where you can find it <a href="http://kcolford.com/the-towers-of-hanoi-2/" rel="nofollow noreferrer">over here</a>. (If that link is inaccessable, try <a href="https://github.com/kcolford/towersofhanoi" rel="nofollow noreferrer">github</a>. Although you'll need access to the necessary tools to build it)</p> <p>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.</p> <p>Any help is very appreciated, thank you in advance.</p> <p><strong>Notice:</strong> This question has been re-posted on Math Overflow <a href="https://mathoverflow.net/questions/153021/correctness-of-proof-about-reves-puzzle">over here</a></p> <p><strong>Notice:</strong> 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 <em>content</em> of the paper rather than the <em>legibility</em> of it. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload