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

About 15 years old · traced to

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 H≅GH\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.

References

Primary source

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

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.