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

$(notxvvy{)}^{{?}^{?}}(xvvz{)}^{{?}^{?}}(yvvnotz)$ is a $2CNF$ formula. $(x,y,z$ are atoms.$)$

It is decidable whether a first order formula is satisfiable.

Assume, that $\underset{n+}{lim}\frac{f(n)}{g(n)}=+$ holds for functions $f,g$:$N{R}_0^{+}.$ Then

$f(n)=(g(n)).$

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

If $q_{0}u|--C$ holds for some uin${}^{+}$and configuration $C$ but $C|--{?}^{**}{C}^{\text{'}}$does not

hold for any accepting configuration $C^{\text{'}},$ then $u!$inL$(M).$

If $A$ is a proper subset of $B,$ then the cardinality of $B$ is greater than the

cardinality of $A.$

$R\frac{E}{\frac{?}{?}}R$ is of continuum cardinality.

If $L!$inR and $L{L}^{\text{'}},$ then $L^{\text{'}}!$inR.

It is known, that $N\frac{P}{\frac{?}{?}}P\frac{O}{?}.$

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

Constructing a deterministic Turing machine of polynomial time complexity

for $2-$COLORING implies that we can construct a deterministic Turing machine

of polynomial time complexity for all languages of NP$.$

If a simple graph $G$ of $9$ vertices has a clique of size $6,$ then the complementary

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

If $PNP,$ then NP$-$intermediate languages exist.

$2$SAT is NP$-$complete.

Every language decidable by a linear bounded automaton can be recognized

by a pushdown automaton.

It is known, that PSPACE is a proper subset of NPSPACE.