Does 2SAT contained in SAT?

Question

Is it true that $2 S A T \subseteq S A T ?$ and in general is $k S A T \subseteq S A T $ where k is any positive integer is true?

Thanks.

Answer 1

Yes.

The definition for SAT is: $SAT:=\{\varphi\in\Sigma^*|\varphi\text{ is a logic formula, and }\exists a.\varphi(a)=True\}$

The definition for kSAT is: $kSAT:=\{\varphi\in\Sigma^*|\varphi\text{ is a 2CNF logic formula (its just a specific form) and }\exists a.\varphi(a)=True\}$

As you can see, from the definition we would have $kSAT\subseteq SAT$.

It's important to note that the 2SAT problem is known to be easy (aka is in $P$), although SAT is not known to be easy, but is known to be $NP-Complete$.

In addition, for every $k\ge 3$, we have $kSAT$ is $NP-Complete$