Complement of languages and coNP
-
05-11-2019 - |
質問
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\}^*?$
正しい解決策はありません