Polynomial Time Computable Structures

[Mario Carneiro]

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/3dd90d0f/attachment-0001.html>