Are two strings equal if all deciders for a language take the same amount of time for both?

Question

Let $X_*^L$ be the set of all deterministic Turing machines $M$ which decide the language $L$ and have the property:

$\forall x,y \in \Sigma^*: t_M(xy) \ge t_M(x) + t_M(y)$ (**)

where $t_M(w)$ is the time of $M$ on input $w$.

Define for all $x,y\in \Sigma^*$:

$d(x,y) := \max_{M \in X_*^L} \frac{|t_M(x) - t_M(y)|}{t_M(xy)+t_M(yx)}$

Then, because of (**) we have $t_M(yx) + t_M(xy) \ge 2(t_M(x)+t_M(y))$ from which it follows that: $\frac{|t_M(x) - t_M(y)|}{t_M(xy) + t_M(yx)} \le 1/2 \frac{|t_M(x)-t_M(y)|}{t_M(x) + t_M(y)} \le 1/2 \frac{ |t_M(x)| + |t_M(y)|}{t_M(x) + t_M(y)} = \frac{1}{2}$ Hence we get $d(x,y) \le 1/2$.

My question is this:

Does $d(x,y) = 0$ which is equivalent to $\forall M \in X_*^L: t_M(x) = t_M(y)$ imply that $x = y$?

The reason for asking this question, is that I am trying to define a metric on strings which has "something to do with the time-complexity of Turing machines". If we define $d(x,y) = \max_{M \in X^L} |t_M(x) - t_M(y)|$ (where the maximum is taken over all machines which decide $L$.). Then I can show, that $d(x,y) = 0$ implies $x = y$. But the problem with this definition, is that $d(x,y)$ can be $\infty$. Or am I wrong with this?

Answer 1

Your "distance" $d(x,y)$ is never zero for distinct, non-trivial $x$ and $y$.

Let $M$ be a decider for $L$ and $x,y \in \Sigma^*$ with $\varepsilon \neq x \neq y$. Let furthermore $T = 1 + \max \{ t_M(x), t_M(y) \}$. Now we construct a machine $M'$ like this:

M'(z) {
  if x == z or xy is a prefix of z
    wait for T steps
  return M(z)
}

We observe that $t_{M'}(x) - t_{M'}(y) \geq T > 0$ since $x \neq y$. Condition (**) is satisfied by increasing the running-time on all inputs that begin with $xy$ as well; hence, $M' \in X^L_*$ and thus $d(x,y) > 0$.

This constructions works for all pairs of distinct $x$ and $y$, proving the claim. Your claim follows since trivially $d(x,x) = 0$ for all $x$.

---

I think the problem is that $d(x,y)$ is not well-defined. With a similar construction as above, we can increase the difference between $t_M(x)$ and $t_M(y)$ by an additional $i$ for all $i \in \mathbb{N}$. Since the sum of $t_M(xy)$ and $t_M(yx)$ grows with $i$ as well (unless either is $\varepsilon$), $d(x,y)$ approaches a constant for $i \to \infty$ and the maxium does not exist.

Answer 2

Raphael's answer explains why $d$ as defined doesn't work. You stated that you want a metric, ideally. To explain why you will have trouble defining it with any kind of max/min relating running time: for every string x in L, there is a machine that first reads in the input, checks if it is x, and if so immediately returns; otherwise it resorts to some "standard" machine's algorithm. Thus, for every x, there is a machine that checks x in linear time.

It is possible to define a metric in runtime on languages, instead of strings. For instance, dividing them into classes such as P, (NP-P), and (Decidable-NP), we can define a metric between two languages that is 1 if they belong to the same class, or 2 otherwise. This of course can be generalized to any number of runtime classes, and this discusses the minimum (over machines) of the supremum (over strings in the language) of runtime, as compared to input length. This gets around the "hard code a given string" problem.

If you really want a metric for strings relevant to their position in the language, min and max clearly don't work, so you must use some type of averaging. This will require defining a measure over machines of interest, or somehow weighting the machines based on their runtimes on other inputs. However, all the constructions I could think of for this would end up very sensitive to the particulars of the construction of Turing machines, or vulnerable to similar "hard coded answer" problems.