The compilation-equivalence characterization conjecture for microcosms

About 11 years old · traced to

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,…,nk∈Nn_1,\dots,n_k\in N such that mm and nin_i agree almost everywhere on XiX_i. Write M≺cNM\prec_{\mathrm{c}}N when every element of MM is compilable in NN, and define

\microcosmm∼c\microcosmn⟺\microcosmm≺c\microcosmn ∧ \microcosmn≺c\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 \microcosmm≺c\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.

References

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.