1
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • $\begingroup$ What is the definition of "complement" that has been given to you? If you do not know, well, there's your problem, look up the definition. If you do have a definition, please mention it here and explain why you it does not help you to solve your problem and we can work from there. $\endgroup$
    – Discrete lizard ♦
    Commented Jan 23, 2019 at 15:58
  • $\begingroup$ @Discretelizard The language containing all strings not in language L is the complement language. (of course, only strings over L's alphabet) $\endgroup$
    – user92484
    Commented Jan 23, 2019 at 16:01
  • $\begingroup$ Well, when talking about problems, languages correspond to problems and strings correspond to problem instances. Does this help you? If not, can you explain why? $\endgroup$
    – Discrete lizard ♦
    Commented Jan 23, 2019 at 16:05
  • $\begingroup$ @Discretelizard exactly, strings represent problem instances. So how can I say that L2 (above) does match the second problem? In other words, how can I say that a non instance of the first problem is automatically an instance of the second problem? $\endgroup$
    – user92484
    Commented Jan 23, 2019 at 16:50
  • $\begingroup$ @Euclid Because $x \in L \iff x \not\in L^c$, where $L^c$ denotes the complement of $L$. This is basic set theory (or simply the definition of "complement", if you are so inclined). $\endgroup$
    – dkaeae
    Commented Jan 23, 2019 at 17:00

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm still scratching my head a bit. Can't we then say that every problems corresponding language is the complement of any other problems corresponding language (since were excluding the not valid instances)? $\endgroup$
    – user92484
    Commented Jan 24, 2019 at 12:06
  • $\begingroup$ @Euclid Problems do not have "corresponding languages". A decision problem is a language. Under the assumption mentioned in the answer, what you are saying is true: both a problem and its complement are valid problems (simply because they are both subsets of $\{0,1\}^\ast$). If they are promise problems, however, things are a bit different (but may be defined in equivalent fashion). $\endgroup$
    – dkaeae
    Commented Jan 24, 2019 at 12:49
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That may be another definition. And so my question is essentially: how can you prove the definitions are equivalent? (The one that I gave and the one that you gave) $\endgroup$
    – user92484
    Commented Jan 23, 2019 at 18:45
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.