ECCC-Report TR23-134https://eccc.weizmann.ac.il/report/2023/134Comments and Revisions published for TR23-134en-usThu, 14 Sep 2023 12:41:03 +0300
Paper TR23-134
| On the complexity of enumerating ordered sets |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2023/134We 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.Thu, 14 Sep 2023 12:41:03 +0300https://eccc.weizmann.ac.il/report/2023/134