how can i say a given problem is in co-NP using it's definition?

Question

I seem to be having trouble understanding the connection between the formal definition of co-NP and how problems are concluded to be in it. co-NP is defined to be the class containing the languages that are complements to languages in NP (I'm using this definition).

So, given this problem: "given a finite set of integers, is there a non-empty subset that sums to zero?" is in NP. How do i conclude that this problem: "given a finite set of integers, does every non-empty subset have a non-zero sum?" is in the class co-NP?

In other words, how do i know that the second problems corresponding language L2 is the complement to the first problems corresponding language L1?

Perhaps i'm missing something fundamental?!

Edit: It seems I was not clear enough so hear is a clarification: My question was why does the complement language L2 represent the second problem if it contains many seemingly random strings?

In other words, how are these seemingly random strings instances of the second problem?

Answer 1

Following the brief discussion in the comments, let me write an answer summarizing it.

When defining decision problems (e.g., based on $\{ 0, 1 \}^\ast$ strings), we usually make the assumption that every word in $\{0,1\}^\ast$ is a valid problem instance. Perhaps your source of confusion is that, usually, this is not made as explicit or given as much importance as it should or, rather, it is only too late (i.e., when discussing complementary problems such as those in $\textbf{coNP}$) that one realizes what the assumption actually entails. Under such an assumption it is obvious why $\textbf{coNP}$ is simply the complements of the problems in $\textbf{NP}$; in fact, without the assumption, such a definition would not make that much sense (since $\textbf{coNP}$ problems would contain invalid problem instances).

In the comments, I have also mentioned the notion of promise problems. This is an alternative way of defining decision problems without needing the aforementioned assumption. Basically, when the input string is not an encoding of a problem instance, the behavior of an algorithm solving the problem is left unspecified. The result is the $\{0,1\}^\ast$ string space being partitioned in three parts: valid "yes" instances, valid "no" instances, and invalid instances. Note that for poly-time algorithms this notion is equivalent to the former one since recognizing a valid instance (for reasonable problems) can always be done efficiently.

Answer 2

NP and co-NP are about decision problems : Problems where every instance has an answer “yes” or “no”.

A problem is in NP if every instance with answer “yes” you has a proof that can be checked on polynomial time. A problem is in co-NP if every instance with answer “no” has a proof that can be checked in polynomial time.

Answer 3

Complement of a decision problem is simply defined as “flip yes and no answers”.

Your confusion seems to come from the fact that decision problems and their corresponding languages are not the same things, strictly speaking. In order to talk about decision problems as languages, you need to formalize them as such.

Whether the complement of the language would be equal to the language of the complement problem is totally up to your chosen encoding of the problem instances.