About the first open question:

The Question (abbreviated):

3SAT-C={all the satisfiable 3CNF formulas for which each variable appears exactly C times (with or without negation) }

It is known that 3SAT-7 is NPC.

We need to show that D-IS = {<G,k>: G has an IS of size k, and for each node in G, it's degree is at most D} is NPC for some D.

In the solution, It is said that the reduction we did in Class from 3CNF to Clique can be as is from 3CNF-7 to n-8 Clique.

n-8 Clique = {<G,k>, G has a clique of size k and for each node in G, it's degree is greater from n-8, while n is the number of nodes}

I think that the reducion we did in class can't be that way, but can be from 3CNF-7 to n-10 Clique:

Each node **isn't** connected to:

1. itself

2. the two other nodes in it's tripple

3. it's neggations.

From the fact that each variabla apperas exactly 7 times, it is possible that all the other 6 appearences of the variable will negate it. So, It is possible for a node to not be connected to 9 other nodes (1 for itself, two for his triplemates and 6 for it's negations).

Why did the solution choose n-8 instead of n-10?

Thanks,

Yoni.