تقرير
On the computability of graphons
| العنوان: | On the computability of graphons |
|---|---|
| المؤلفون: | Ackerman, Nathanael L., Avigad, Jeremy, Freer, Cameron E., Roy, Daniel M., Rute, Jason M. |
| سنة النشر: | 2018 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Logic, Computer Science - Logic in Computer Science, Mathematics - Combinatorics, Mathematics - Probability |
| الوصف: | We investigate the relative computability of exchangeable binary relational data when presented in terms of the distribution of an invariant measure on graphs, or as a graphon in either $L^1$ or the cut distance. We establish basic computable equivalences, and show that $L^1$ representations contain fundamentally more computable information than the other representations, but that $0'$ suffices to move between computable such representations. We show that $0'$ is necessary in general, but that in the case of random-free graphons, no oracle is necessary. We also provide an example of an $L^1$-computable random-free graphon that is not weakly isomorphic to any graphon with an a.e. continuous version. Comment: 24 pages, 1 figure |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1801.10387 |
| رقم الأكسشن: | edsarx.1801.10387 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |