1
$\begingroup$

By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.

$L^c$ is said to be the complement of the language, and it seems to be defined as follows - $\forall w, w\in L \implies w \notin L^c$ and $w \notin L \implies w \in L^c$.

Equivalently, according to Arora and Barak's book "Computational Complexity: A Modern Approach", $L^c = \{0,1\}^* - L$.

I will demonstrate my question with an example - The definition of the complexity class $coNP$ is, as per Arora and Barak's book, $coNP = \{L : L^c \in NP \}$.

But if we take a specific case, lets say

$SAT = \{f(x_1, x_2,\cdots,x_n) : \exists x \in \{0,1\}^n f(x) = 1\}$,

then the $coNP$ counterpart is supposed to be

$\overline{SAT} = \{f(x_1,x_2,\cdots,x_n) : \forall x \in \{0,1\}^n f(x) = 0\}$

Which means, $\overline{SAT}$ contains all the boolean formulae that are false for all inputs.

According to the definitions above though $(L^c = \{0,1\}^* - L)$, lots of random words should be included in the language $\overline{SAT}$ that are not even "well formed" boolean formulae to begin with.

Should the complement be over all boolean formulae instead of $\{0,1\}^*$?

Is the complement of every language always defined over a subset of words that are "well formed" instead of having been defined over $\{0,1\}^*?$

$\endgroup$
2
$\begingroup$

The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all.

In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, recognising which strings are valid encodings is computationally very easy. For any such encoding, the computational complexity of the two languages $$\{w\mid w\text{ encodes an unsatisfiable formula}\}$$ and $$\{w\mid w\text{ encodes an unsatisfiable formula or is not a valid encoding}\}$$ is the same, so we tend not to distinguish between them.

Alternatively, it's usually fairly straightforward to come up with an encoding where every string is a valid encoding of some input. For example, consider a problem whose input is a graph. Naïvely (and normally!) we would encode a graph as the binary listing of its adjacency matrix. However, that means that only inputs whose length is a perfect square are valid. We could make every string valid by adding zeros to the end until the length is a perfect square so that, e.g., the string $01101$ would encode the graph whose adjacency matrix is $$\left(\begin{matrix}0&1&1\\0&1&0\\0&0&0\end{matrix}\right).$$ If our input is supposed to be an undirected graph, that's still no good, since the matrix isn't symmetric. In that case, we could just encode the entries above the diagonal, again padding with zeros to reach the next triangular number. In this encoding, $01101$ would encode the graph with adjacency matrix $$\left(\begin{matrix}0&0&1&1\\0&0&0&1\\1&0&0&0\\1&1&0&0\end{matrix}\right).$$

But translating between these inputs is easy (it can be done in, e.g., deterministic logspace), so we usually just ignore these fine details.

$\endgroup$
  • $\begingroup$ Thank you! This makes sense. But if we strictly follow the definition of the complement you gave in the first paragraph, then the languages (decision problems) in the set coNP will contain all kinds of strings that do not represent boolean formulas at all, hence my confusion. $\endgroup$ – pkwssis Aug 5 at 13:32
  • $\begingroup$ I do know though that there is a way to define co-NP to avoid this mess altogether!! Sorry for grammar mistakes, english is not my first language $\endgroup$ – pkwssis Aug 5 at 13:33
  • 1
    $\begingroup$ @pkwssis Your confusion is understandable. In practice, though, this isn't a big issue, which is good, because there's no way of "fixing" it. Regardless of what one might want co-NP to be, languages such as "the set of binary strings that either aren't the adjacency matrix of an undirected graph, or are the adjacency matrix of an undirected graph that has no Hamiltonian cycle" are going to be in co-NP. The only question is whether one considers that to be the complement of the Hamiltonicity problem. $\endgroup$ – David Richerby Aug 5 at 13:42
  • $\begingroup$ Yes, thanks for clearing up the confusion!! $\endgroup$ – pkwssis Aug 5 at 14:05
1
$\begingroup$

As I understand it, you are interpreting the space $\{ 0,1 \}^\ast$ to be the (disjoint) union of $F$ and $\overline{F}$, where $F$ is the set of valid formulas and $\overline{F}$ is the set of strings which do not encode a formula (according to some unspecified encoding). Then, in your perspective, we should have that $F = \textsf{SAT} \cup \overline{\textsf{SAT}}$ is the (disjoint) union of satisfiable and not satisfiable formulas.

However, that is not how things usually work.

The standard convention is to take the set $\{ 0,1 \}^\ast$ and associate each string in it with a formula, thus yielding a map $f$ from $\{0,1\}^\ast$ to the set of (valid) formulas. Additionally, $f$ should be efficiently computable as well as a bijection (or at least a surjection). Since $f$ is a map (i.e., a function), you get that each binary string (possibly uniquely) encodes a problem instance of $\textsf{SAT}$ (or its complement). Hence, $\overline{F}$ is empty, and everything is good.

In the particular case of the Arora and Barak book, refer to section 2.3. In their definition, they do admit "invalid" formulas, but rewire things so that each such formula actually stands for "some fixed formula" (see footnote 3). That is, their $f$ is indeed a surjection (which turns out not to be a bijection, though only for convenience) and in their definition you also do not have any string in $\overline{F}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.