The norm-one btt obstruction for intrinsically n-approximable distance functions
The norm-one btt obstruction for intrinsically n-approximable distance functions
Let be a computable connected graph whose distance function is intrinsically -approximable from above, where . A function is -approximable from above if it has an approximation from above with at most changes at each input. For computable functions and , write ? Norm-one btt obstruction conjecture. There \exists a function which is -approximable from above such that, for every computable graph with distance function , . This would establish that norm 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
Sign in to submit a solution.
No solutions have been posted yet.