Polynomial Time Computable Structures

[Mario Carneiro]

Actually, the Calkin-Wilf tree (
https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree) a variation on the
Stern-Brocot tree that has a simpler function for getting the children, and
the wiki page goes into how to calculate the nth element of the sequence
explicitly. (Both methods only cover positive rationals, but it's easy to
patch that up by alternating negatives.)

On Wed, Dec 8, 2021 at 11:11 PM Mario Carneiro <di.gama at gmail.com> wrote:

> You can use the Stern-Brocot tree (
> https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) to biject
> between rational numbers and bit strings, which should yield a polynomial
> time algorithm for the nth rational number.
>
> On Wed, Dec 8, 2021 at 8:05 PM JOSEPH SHIPMAN <joeshipman at aol.com> wrote:
>
>> 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.
>>
>> If this has a negative answer, then the definition of “polynomial time
>> computable structure” becomes problematic.
>>
>> The standard enumerations of the rationals, where you enumerate the
>> fractions and cross off the ones not in reduced form, aren’t computable in
>> polynomial time in this sense unless factoring integers is polynomial time.
>>
>> If the “Nth prime” function were computable in time polynomial in the
>> length of N, then I could make an enumeration of the rationals (without
>> repetitions) which is fast enough.
>>
>> If there is no such enumeration, then, even though the canonical form of
>> rationals as finite strings over an alphabet consisting of finitely many
>> numerals, “-“, and “/“is polynomial time computable and the arithmetic
>> operations on such canonical forms are polynomial time computable, there
>> doesn’t seem to be a presentation in terms of “polynomial time computable
>> functions on the natural numbers”, so that the structure of rationals is
>> somehow essentially more computationally complex than the structure of
>> natural numbers or the structure of integers.
>>
>> Of course, there’s no problem if you don’t insist on having a polynomial
>> time bijection with the natural numbers. For the rationals we don’t care so
>> much, because the “reduced forms” are so dense in the space of “fractions”
>> that we aren’t sacrificing anything significant in terms of time
>> complexity. But for a structure with a notation system whose reduced or
>> canonical forms are sparse, it makes a difference.
>>
>> — JS
>>
>> Sent from my iPhone
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211208/09f3fb7d/attachment-0001.html>