Is it true? Write $Y=$ yes or $N=$ no into the box corresponding to the statement.

$(notxvvyvvz{)}^{{?}^{?}}$not$(xvvyvvnotz)$ is a $3$CNF formula. $(x,y,z$ are atoms.$)$

It is decidable whether two context$-$free grammars generate the same language.

${57}^n=({74}^n)$

Let $M=($:$Q,,,,q_0,q_a,q_r$:$)$ be a one tape nondeterministic Turing machine.

If $q_{0}u|--C_1$ holds for some uin${}^{+}$and we have $C_i|--C_{i+1}$ for all natural

numbers $i1,$ then are configurations of $\{$:$M).$

If there is an injective mapping from $A$ to $B,$ then the cardinality of $B$ is

greater than the cardinality of $A.$

If $L^{\text{'}}$inR and $L^{\text{'}}{?}_{p}L,$ then LinR.

Let $D$ be an instance of the Post Correspondence Problem. Then every solution

of $D$ consists of at most $|D|$ dominoes.

We know, that for all languages LinNP there exist a deterministic Turing

machine $M$ satisfying $L(M)=L.$

Constructing a deterministic Turing machine of polynomial time complexity

for TSP implies that we can construct a deterministic Turing machine of poly$-$

nomial time complexity for all languages of NP$.$

If a simple graph $G$ of $8$ vertices has a clique of size $3,$ then the complementary

graph of $G$ has a an independent set of size $5.$

$P$NPLongleftrightarrow there exists an NP$-$intermediate language.

$L_{PCP}$ is in NP$.$

Linear bounded automata are specific deterministic Turing machines.

The class of languages, that can be recognized by a linear bounded automaton

contains the class of languages that can be recognized by a pushdown automa$-$

ton.

All languages of NPSPACE are decidable by a deterministic Turing machine.