New answers tagged reference-request
9
Maybe the keyword you are looking for is "Implicit Complexity". It is more general than Curry-Howard correspondence, but several lines of research investigate along the axis you are interested in. You can check for instance the publications of Patrick Baillot for many references and pointers.
For a little self-promotion, here are for instance two ...
0
The set of computable real functions is also recursively enumerable. Assume it is enumerated by $(f_i)_{i\in\omega}$. Then the Solomonoff prior of $f_i$ is $p(f_i)=2^{-K(i)}$. So there is no difference whether the function is defined over natural numbers or real numbers, as long as it is computable.
2
It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.
0
After a bit more searching, it appears that what I'm looking for is unlikely to exist.
In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when ...
Top 50 recent answers are included
