Definition of $coNP$

Question

I have this question about the definition of $coNP$ in our lecture that I simply cannot wrap my head around. We define $$ coNP := \{L \subset \{0,1\}^* \mid \bar{L} \in NP\},$$ and then later on we give as an example $\bar{SAT} = \{\varphi \mid \varphi \text{ is unsatisfiable}\}$. Now this makes no sense to me:

Firstly if we look at $\{0,1\}^*$ then couldn't the same binary string mean two completely different things depending on the semantics we choose to encode the instances? For examples $01$ could encode an empty graph or a graph with a single vertex or whatsoever). Also couldn't many binary strings lead to the same instance depending on semantics? for example by saying $0 = 00$.

Secondly, specifically for $\bar{SAT}$, why is it exactly the unsatisfiable formulas given the definition? Shouldn't the complement of $SAT$ when seen as a subset of $\{0,1\}^*$ contain a lot of garbage that could not even be interpreted as formulas?

Somehow it seems that the intuition for $coNP$ as used for $\bar{SAT}$ just does not match its definition, which should be crucial for a better understanding of the class?

Maybe I'm getting some things wrong here so I'm glad if you could lead me out of this confusion.

Apologies! I see now that you did use MathJax, but some of the results looked a bit odd: \overline{SAT} or even better \overline{\mathrm{SAT}} give better results than \bar{SAT} ($\overline{SAT}, \overline{\mathrm{SAT}}, \bar{SAT}$). — Rob Arthan, Sep 17 '21 at 19:43

Rob Arthan · Accepted Answer · 2021-09-19T16:52:37.100

1

For you first point, in the definition of $\mathrm{co}\mathrm{NP}$, $L$ is just a set of strings of $0$s and $1$s - it doesn't matter what a string "encodes".

For your second point, you are right that $\overline{\mathrm SAT}$ viewed as a set of sequences of symbols contains a lot of syntactic junk. However, it takes only polynomial time to parse the sequences and identify the junk, so it doesn't make any difference to questions about whether the original problem is in $P$ or $NP$.

I am afraid I don't understand your last point about intuitions about $\mathrm{co}\mathrm{NP}$ and $\mathrm{SAT}$.

edited Sep 19 '21 at 16:52

answered Sep 17 '21 at 00:09

Rob Arthan

48,577

I think my problem with the encoding is as follows: If we find a language $L\subset {0,1}^$ that is $NP$-complete. And say we know that $L$ is in bijection with ${0,1}^$ then wouldn't this imply that $NP = P$, since we can easily decide ${0,1}^*$? – 0CT0 Sep 17 '21 at 11:07
The existence of that bijection would just tell you that $L$ is not finite. The bijection doesn't give you a reduction of the decision problem for $L$ to another decision problem (for that you need to take into the complement of $L$ as well). – Rob Arthan Sep 17 '21 at 19:38

Definition of $coNP$

1 Answers1