Are you interested in allowing the algorithm to be randomized?

Assuming that is correct, KC seems to be no "harder" than halting, which makes Manin's comment quite mystifying to me (but I don't know Russian, so I don't know the context of the quote).

@Alexey, I think if we have an oracle to solve the halting problem, we can compute Kolmogorov complexity: On input $s$, let $m$ be the length of $s$ plus the size of the TM that copies input to output (this is an upper bound on $KC(s)$); now iterate over the finitely many pairs (TM, input) with total length less than $m$, first checking if this TM halts on this input, and if so, running it to see if it produces $s$. Output the length of the shortest pair that produces $s$, or output $m$ if none do.

My simulations give an average minimum distance of very close to 1/n (and nowhere near $1/\sqrt{n}$) for n in [20, 40, 80, 160, 320, 640, 1280]. The minimum distances, averaged over ten thousand trials at each value of n, were [0.0515, 0.0245, 0.0120, 0.00599, 0.00296, 0.00147, 0.000738]. For comparison, 1/n is [0.05, 0.025, 0.0125, 0.00625, 0.003125, 0.0015625, 0.00078125] and $1/\sqrt{n}$ is [0.224, 0.1587, 0.112, 0.079, 0.056, 0.040, 0.028].

What does "numerical simulation" mean?

@Ilya, not sure, but I thought there might exist relevant literature because it seems like an extreme case ... mainly, we can take the discrete metric ($\rho(x,y) = 1 \iff x \neq y$) and then Wasserstein distance should be $\mathbb{P}(X^2 \setminus \Delta_X)$ ...

@Tino, ok, but if you are visiting $o(n)$ vertices and making $o(n)$ modifications (where $n$ is the number of vertices), it still seems very unlikely to me.

I'd guess that what you're asking is too difficult, unless we have a DAG. One intuition is that, if we cannot remember which vertices we've visited, then it will be difficult to distinguish between a small cycle and a very long line.

(hope my notation makes sense.) @Ilya, I don't know of any literature, but maybe the keyword "Wasserstein metric" helps (although the metric is defined for probability distributions). en.wikipedia.org/wiki/Wasserstein_metric

@Dirk, it should, I think, be a measure $\mu$ on $X^2$ such that $\int_{y \in X} d\mu(x,y) = P(x)$ and $\int_{x \in X} d\mu(x,y) = \tilde{P}(y)$.

@ManfredWeis, maybe I didn't express it well, but I'm just trying to say that it sounds like you are doing the same thing as the FFT algorithm, except with a different choice of basis. If that's true (or even if not), you could look at the general Fourier transform approach to see if it could give the construction you're looking for.

Are you familiar with polynomial-time approximation schemes (en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)? They seem to fit your definitions to me (i.e. let $i = 1 - \epsilon$).

This kind of issue may be one reason that we relax the notion of "efficient" to "polynomial-time computable"; it seems to generally be nicely model-independent.

@Christoph - no, Rice's theorem says we cannot decide nontrivial things about a the language of a program, but #1,3,4 do not deal with the program's language and #2 does not get programs as input.

Most (almost all?) graduate computer science courses I am familiar with follow this format; it seems usually quite successful. Often, students are encouraged to work on projects in groups of two, maybe three. A difference might be in CS that open problems are easier to identify and approach, but it seems like the approach could be very good in maths as well.

@DavidSpeyer - agreed, my bad: I hastily read "rational function" and thought "rational-valued function".