## [comp_complex] Solutions

• From: David Friedman <dkf@xxxxxxxxxx>
• To: <comp_complex@xxxxxxxxxxxxx>
• Date: Mon, 12 Apr 2004 15:55:29 -0400 (EDT)

```hi everybody,

for the assignment due on Wednesday you are allowed to use a
package such as Mathematica, MatLab, etc. to do the matrix
manipulations.

Also, at the end of the first problem please write all

Basic solutions for the last assignment:

1. The simplification is all seven clauses other than:
(~pi_1 \/ ~pi_2 \/ ~pi_3)

anded together.

1.1. At a minimum 1/2 of the phi_psi,r are false, and for each
phi_psi_r there are at most 7 clauses of which at a
minimum only one clause is false, so the minimum
fraction of clauses that are false is
1/14. Meaning the machine should accept if more than 13/14
of the clauses are satisfiable, so epsilon = 1/13.

2. To prove: w(G) = m ===> w(G^2) >= m^2

The original clique is v_1 ... v_m   so then
under the definition (v_1, v_1) .... (v_m, v_m) are
all connected.

To prove:  w(G^2) = m^2  ===> w(G) >= m

Consider the m^2 nodes which form the clique:
-    -
| |  | |
w_1    =   (| |, | |  )
w_2    =   (| |  | |  )
...         | |  | |
w_m^2  =   (| |  | |  )
-    -

There must be at least m distinct nodes in either the
first column or the second column (otherwise there
would be duplicates in the list), and all these m
nodes are connected.

The two statements combined prove the the theorem, (for if
when w(G) = m  w(G^2) > m^2 would imply from the second that
w(G) > m, and similarly the other way)

3. This problem just asks you to show that the expression accurately
represents the problem.

```