On the complexity of enumerating ordered sets

Webpage for a paper by Oded Goldreich


Abstract

We consider the complexity of enumerating ordered sets, defined as solving the following type of a computational problem: For a predetermined ordered set, given $i\in\N$, one is required to answer with the $i^{th}$ member of the set (according to the predetermined order).

Our focus is on countable sets such as the primes and the rational numbers, although in these cases we provide no decisive answers. In general, we do not report of any exciting results, but rather make a few observations and suggest some open problems.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.