The norm-one btt obstruction for intrinsically n-approximable distance functions

From papers

Let GG be a computable connected graph whose distance function is intrinsically nn-approximable from above, where n>0n>0. A function is nn-approximable from above if it has an approximation from above with at most nn changes at each input. For computable functions ff and gg, write fototeg?1-bttgf ot ot eg?_{1\text{-}{\texttt{btt}}}g? Norm-one btt obstruction conjecture. There \exists a function ff which is nn-approximable from above such that, for every computable graph HGH\cong G with distance function dHd_H, dH̸1-bttfd_H\not\equiv_{1\text{-}{\texttt{btt}}} f. This would establish that norm 22 is intrinsically necessary in the btt-reductions between such distance functions and the functions they encode, rather than merely an artifact of the known constructions. The conjecture is presented as an open question in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Wesley Calvert, Russell Miller and Jennifer Chubb Reimann, “The Distance Function on a Computable Graph”, arXiv:1111.2480 (2011).

Solutions 0

No solutions have been posted yet.