Polynomial Time Computable Structures

[JOSEPH SHIPMAN]

It’s not clear to me that that gives a bijection between natural numbers and rationals which is polynomial time in both directions (although one of the earlier answers did give one).

Sent from my iPhone

> On Dec 9, 2021, at 8:43 PM, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
> 
> 
> If I've correctly understood Joseph Shipman's "I would like to have an enumeration without repetitions of the rationals in which the Nth rational number is computable in time polynomial in the length of N, rather than time polynomial in N." dated Wed, 8 Dec 2021 18:51:46 -0500, then I would expect a number of people to point out that the Farey fractions accomplish this very neatly.
> 
> With parallel computing one can do even better, generating 2ᵐ + 1 rationals in the interval [0,1] without repetition in m steps.  At step m = 0, initialize the process with the 2⁰ + 1 = 2 rationals 0/1 and 1/1.  At each subsequent step, between consecutive rationals a/c and b/d, interpolate (a+b)/(c+d).  So at step m = 1 we have 1/2, bringing the count to 2¹ + 1 = 3, then at the second step 1/3 and 2/3 bringing the count to 4 + 1 = 5, then at the third step 1/4, 2/5, 3/5, and 3/4 (so 8 + 1 = 9 rationals), and so on.
> 
> It is well known that this process enumerates all reduced rationals without repetition (use the fact that consecutive rationals viewed as a 2x2 matrix always have determinant -1, preserved by elementary column operations).  Better yet, at every step those enumerated so far are in increasing order.  And it should be obvious that after step m there are 2ᵐ gaps, which step m+1 splits into two gaps for the obvious proof by induction.
> 
> Vaughan Pratt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211209/f682ff00/attachment-0001.html>