The compilation-equivalence characterization conjecture for microcosms

Let \microcosmm\microcosm{m} and \microcosmn\microcosm{n} be microcosms. A measurable map mm is compilable in a set of measurable maps NN if there is a finite partition X1,,XkX_1,\dots,X_k and maps n1,,nkNn_1,\dots,n_k\in N such that mm and nin_i agree almost everywhere on XiX_i. Write McNM\prec_{\mathrm{c}}N when every element of MM is compilable in NN, and define

\microcosmmc\microcosmn\microcosmmc\microcosmn  \microcosmnc\microcosmm.\microcosm{m}\sim_{\mathrm{c}}\microcosm{n}\quad\Longleftrightarrow\quad \microcosm{m}\prec_{\mathrm{c}}\microcosm{n}\ \wedge\ \microcosm{n}\prec_{\mathrm{c}}\microcosm{m}.

Let C[\microcosmm]\mathtt{C}[\microcosm{m}] denote the complexity class associated with the microcosm \microcosmm\microcosm{m}.

Compilation-equivalence characterization conjecture. If

\microcosmm̸c\microcosmn,\microcosm{m}\not\sim_{\mathrm{c}}\microcosm{n},

then

C[\microcosmm]C[\microcosmn].\mathtt{C}[\microcosm{m}]\neq\mathtt{C}[\microcosm{n}].

The preceding theorem proves the inclusion C[\microcosmm]C[\microcosmn]\mathtt{C}[\microcosm{m}]\subset\mathtt{C}[\microcosm{n}] when \microcosmmc\microcosmn\microcosm{m}\prec_{\mathrm{c}}\microcosm{n}. The conjecture asserts that non-equivalent microcosms always induce distinct complexity classes, giving a converse characterization of the compilation preorder.

Sources & referencesView supporting material

Primary source

Thomas Seiller, “Towards a Complexity-through-Realisability Theory”, arXiv:1502.01257 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.