Question 9:

A cnf formula is 'long' if it has at least 2^(n/2) clauses where n is the number of variables. LongSat is the language of all satisfiable LongCNF formulas.

How is that in P? What is the algorithm for deciding it in polinomial time?

Question 8:

For a turing machine M H(M) is {x| where M halts in x}.

I am having a hard time understanding why one answer is right (A):

A. If H(M) is in R then L(M) is in R. That makes sense as if M halted on input x we can check if it is in the accepting state.

And the other one (B) is wrong:

B. If L(M) is in R then for every input x for M, we know that M halts and either accepts or rejects, and therefore we know that if L(M) is in R then M halts for every input making H(M) decidable!

What am I missing?

Question 7:

Am I to understand that the first Clip is important but all the others do not add more abilities? If Ck=Cm for every m>k then what about m=1 and K=0 where they are not the same. That's a contradiction.

Question 6:

L={<G,R,S>| L(G)intersection with L(R)=L(S)} where R and S are regular expressions and G is a CFG. why is L in co-RE\R?

The intersection of a CFL and a regular language is regular and then we get EQdfa which is in R.