Polynomial Time Computable Structures

[JOSEPH SHIPMAN]

That’s very helpful, thanks. So the rational numbers represent a “polynomial time computable structure” no matter how you define that term.

But there’s still an interesting distinction between structures whose points are represented by finite terms or strings with polynomial time computable functions and relations and a polynomial time computable equivalence relation (or, slightly stronger, polynomial time computable canonical forms), and one where there is a polynomial time bijection of the points with the natural numbers. Does anyone know an example of the former that is not known to be the latter?

— JS

Sent from my iPhone

> On Dec 8, 2021, at 11:21 PM, Mario Carneiro <di.gama at gmail.com> wrote:
> 
> 
> 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/20211209/2404b148/attachment-0001.html>