Polynomial Time Computable Structures

[JOSEPH SHIPMAN]

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/8e506952/attachment-0001.html>