How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages

Question

I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L} = \{ \overline{L} \mid L \in \mathcal{L} \}$$

and where $\overline{L}$ is the complement. From what I read in an earlier part of my textbook, the complement of $L$ is equal to $\Sigma^* - L$.

However, say that $\mathcal{L}$ is NP. An instance of a language $L$ that is in $\mathcal{L}$ is the set of graphs with Hamiltonian paths. However, in this case, its complement $\bar{L} \in$co-$\mathcal{L}$ is the set of graphs without Hamiltonian paths, i.e. $\bar{L} \in $co-NP.

But is the set of graphs without Hamiltonian paths equal to $\Sigma^* - L$ (following the definition of complement) ? In this case, we would be including some strings $\in \Sigma^* - L$ that do not represent graphs.

Another example is $A_{TM}$, which represents the language

$$\{\langle M,w\rangle \mid M \text{ accepts input } w \}$$

In this case, does $\overline{A_{TM}}$ represent $\Sigma^* - A_{TM}$?. If this is the case, we would be including in $\overline{A_{TM}}$ several strings that do not represent TM's, or that refer to other input that is not equal to $w$. Or rather, does $\overline{A_{TM}}$ represent the language

$$\{\langle M,w \rangle \mid M \text{ diverges on input } w \}$$

Answer 1

We typically think of instances to problems as being in some format. There are several ways to think of this. Consider for example $A_{TM}$, in which the input is a pair $\langle M,w \rangle$. The three most obvious are:

1. Every input string can be decoded into an input pair $\langle M,w \rangle$.
2. Inputs not of the form $\langle M,w \rangle$ don't belong to the language.
3. We think of $A_{TM}$ as a promise problem: inputs $\langle M,w \rangle$ where $M$ accepts $w$ are Yes instances, inputs $\langle M,w \rangle$ where $M$ doesn't accept $w$ are No instances, and we don't care about other inputs.

If you take complementation, here is what you get under each interpretation:

1. $\overline{A_{TM}}$ consists of all inputs strings which, when decoded to $\langle M,w \rangle$, are such that $M$ doesn't accept $w$.
2. $\overline{A_{TM}}$ consists of inputs not of the form $\langle M,w \rangle$, and of those of the form $\langle M,w \rangle$ such that $M$ doesn't accept $w$.
3. $\overline{A_{TM}}$ is the promise problem corresponding to option 1.

While these different interpretations look different, in practice the difference is very slight, given that it is easy to recognize that the input is of the correct format. For example, given interpretation 2, consider the following two languages: $\overline{A_{TM}}$, and $\widetilde{A_{TM}}$, the language of all pairs $\langle M,w \rangle$ such that $M$ doesn't accept $w$. These two languages differ in malformed inputs, that is, outputs not of the form $\langle M,w \rangle$. Since such inputs are easy to detect, we have an algorithm for $\overline{A_{TM}}$ iff we have one for $\widetilde{A_{TM}}$, and furthermore, the complexity of both algorithms is very similar.

For this reason, we typically ignore such issues, and implicitly work under the "promise problem" interpretation: the input is assumed to be of the form $\langle M,w \rangle$. Purists can think of the first interpretation instead, which from this point of view behaves identically.

More generally, whatever interpretation you choose, you still formally have to describe what encoding is used for $\langle M,w \rangle$. We typically don't bother, since all reasonable interpretations are inter-reducible, and so don't change the computability or complexity of the problem. That said, the difference between weak NP-hardness and strong NP-hardness lies exactly in which input representation is being used.