質問

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\}^*?$

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top