User khaaan - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T09:36:34Z http://mathoverflow.net/feeds/user/30816 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119453/polynomial-time-algorithm-to-compare-numbers-in-conway-chained-arrow-notation Polynomial-time algorithm to compare numbers in Conway chained arrow notation khaaan 2013-01-21T09:58:32Z 2013-03-18T16:22:00Z <p>I am looking for a <b>polynomial-time</b> algorithm which, given a character string containing two numbers in <a href="http://en.wikipedia.org/wiki/Conway_chained_arrow_notation" rel="nofollow">Conway's chained arrow notation</a> for large numbers, indicates whether the first number is less than, greater than, or equal to the second. </p> <p>Suppose the function is called C. Then</p> <ul> <li> C("1→2→3→4 ? 4→3→2") should yield "&lt;", since 1→2→3→4 = 1 &lt; 4<sup>256</sup> = 4→3→2, <li> C("2→4→3 ? 4→3→2") should yield "&gt;", since 2→4→3 = $2^{2^{\cdot^{\cdot^2}}}$ (a tower of exponents of height 65536) &gt; 4<sup>256</sup> = 4→3→2, and <li> C("2→2→3 ? 2→2→2→6") should yield "=", since 2→2→3 = 4 = 2→2→2→6. </ul> <p>Does such a thing exist?</p> http://mathoverflow.net/questions/119453/polynomial-time-algorithm-to-compare-numbers-in-conway-chained-arrow-notation/119465#119465 Comment by khaaan khaaan 2013-01-21T13:25:11Z 2013-01-21T13:25:11Z I love hypercalc, but it doesn't support Conway notation.