Polynomial Time Computable Structures

[JOSEPH SHIPMAN]

I am interested in practical computation. We don’t use tally notation, we use base_n for various n>=2, and it is very easy to recognize a natural number in a canonical form (finite nonempty string over an n-symbol alphabet, n>=2, where the alphabet includes the symbol “0”, whose first member is not the symbol “0” if  the string has length >1) and to compute the arithmetic operations in polynomial time.

By  a polynomial time structure I mean the strongest reasonable sense: polynomial time computable functions and relations on strings representing elements, polynomial time recognition of unique canonical forms, and polynomial time bijections inverse to each other mapping between the natural numbers expressed in base_n  and the set of unique canonical forms. The only fuzziness here is whether there needs to be a growth condition so that the canonical forms are not too sparse or too long relative to the natural numbers they are mapped to.

— JS

Sent from my iPhone

> On Dec 13, 2021, at 1:08 PM, Calvert, Wesley C <wcalvert at siu.edu> wrote:
> 
> 
> 
> One of the (well-known) difficulties inherent in the question is what, exactly, we mean by the natural numbers.  There is a structure in tally notation which is classically (and even computably) isomorphic to the natural numbers in base-10 (or base-n for n>=2), but not polynomial-time (or even, if I remember right, PSPACE) isomorphic.
> 
> --
> Wesley Calvert
> Associate Professor and Director of Undergraduate Programs
> School of Mathematical and Statistical Sciences
> Mail Code 4408, Southern Illinois University
> 1245 Lincoln Drive, Carbondale, Illinois 62901
> Office: (618) 453-6582
> Mobile: (618) 534-8457
> 
> 
> ________________________________________
> From: FOM <fom-bounces at cs.nyu.edu> on behalf of JOSEPH SHIPMAN <joeshipman at aol.com>
> Sent: Thursday, December 9, 2021 8:12 PM
> To: Vaughan Pratt
> Cc: FOM at cs.nyu.edu
> Subject: Re: Polynomial Time Computable Structures
> 
> [EXTERNAL EMAIL ALERT]: Verify sender before opening links or attachments.
> 
> 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