Homework #8 Solution

Description

1. Reductions

Let A B for two problems A and B mean that problem A can be solved in big O of the time it takes to solve problem B.

1. Show that MULTIPLICATION SQUARING.

2. Show that SQUARING MULTIPLICATION.

3. Show that SQUARING RECIPROCAL.

4. If A ⌘ B means A B and B A which of MULTIPLICATION, SQUAR-ING, and RECIPROCAL are equivalent ?

HINT: _x¹ − _y¹ = ^y_x⁻_y^x . Try y = x + 1.

2. Lucas Numbers:

INPUT: A K bit number X.

QUESTION: Is X a Fibonacci number?

The Lucas numbers are defined by the recurrence

Ln = Ln−1 + L n−2

with the initial conditions: L₀ = 2, L₁ = 1 Show that this problem is in P by out-lining (NO CODE, just explain what you’re doing) an algorithm, AND showing that your algorithm runs in polynomial time in K, the number of bits.

3. Roots:

Without finding the solutions, show that x² − x − 1 = 0 has:

1. 1. NO positive integer solutions

1. 2. NO rational solutions

HINTS:

1. 1. 1. Assume that x = p/q where p and q are integers with no common factors.

1. 1. 2. p² − q² = (p − q) (p + q).

1. 1. 3. Each integer is either ODD or EVEN.

4. Average Case:

Do Exercise 5.25 in the NOTES on page 61.

5. Lower Bound:

Exercise 6.1 in the NOTES on page 71, is about the lower bound of ³₂ n − 2 comparisons to find the largest and smallest elements in an array. Devise a divide-and-conquer algorithm for this problem and show that the number of comparisons used by your algorithm achieves this lower bound.

6. Boolean Expression:

Assume that you have an algorithm YS( ) so that when you input a Boolean expression E(x₁, . . . , x_n) into YS( ) ,

YS( E ) outputs YES if E is satisfiable, and YS( E ) outputs NO if E is not satisfiable.

1. 1. Show how to use YS( ) to construct an algorithm FIND( D(x₁, . . . , x_n)) which when given a satisfiable Boolean expression D(x₁, . . . , x_n), returns an assignment x₁ = a₁, x₂ = a₂, . . . , x_n = a_n, so that D(a₁, . . . , a_n) is TRUE.

1. 2. Assume that YS( D(x₁, . . . , x_n) ) has run time O( n^k ) and find the run time of FIND( D(x₁, . . . , x_n) ) .

7. Platonic Hamiltonian Circiuts:

Show that each of the PLATONIC solids has a Hamiltonian circuit.

8. s-t Hamiltonian Path:

INPUT: A graph G and two specified vertices s and t.

QUESTION: Does G have a Hamiltonian Path which starts at s and ends at t?

1. 1. Assume that you know that Hamiltonian Circuit is N P −Complete, show that s-t Hamiltonian Path is N P −Complete.

1. 2. Assume that you know that s-t Hamiltonian Path is N P −Complete, show that Hamiltonian Circuit is N P −Complete.

1. 3. Show that the Yes/No version of TSP (Traveling Sales Person) with all edge weights in {1, 2} is N P −Complete. (You should assume that Hamiltonian Cir-cuit is N P −Complete.)

9. Graph Isomorphism:

Graph isomorphism is an example of a problem which is in N P, but is not known to be N P-complete, nor is it known to be in co-N P.

INPUT: Two graphs, G₁ = (V₁ , E₁) and G₂ = (V₂ , E₂).

QUESTION: Can the vertices of G₁ be renamed so that G₁ becomes G₂? (Is there a

one-to-one onto function f : V₁ ! V₂ so that 8x, y (x, y) 2 E₁ i↵( f(x), f(y) ) 2 E₂? Show that GRAPH ISOMORPHISM is in N P.

10. Canonical Number:

A graph with n vertices can be represented as an n ⇥ n binary matrix which has a 1 in position (i, j) if and only if there is an edge (v_i, v_j ). If you “unroll” this matrix (say by rows), you will have a vector of n² bits and you can consider this to be a number in standard binary notation. So, there is a correspondence between n vertex graphs and n² bit numbers. If we re-label the vertices of the graph, we don’t change the graph properties. Di↵erent re-labelings of the graph will (usually) give di↵erent numbers. Clearly among all re-labelings of the graph, there is some re-labeling which gives the smallest value for this binary number. We would like to represent a graph by the minimum number we can get by re-labeling. We’ll call this minimal number the canonical number of the graph. It’s easy to see that two graphs are isomorphic i↵they have the same canonical number.

(a) The graph v₁ — v₂ — v₃ is isomorphic to v₁ — v₃ — v₂ and is also isomorphic to v₂ — v₁ — v₃.

Find the canonical number of v₁ — v₂ — v₃.

1. 2. Show that if finding the canonical number of a graph is easy, then GRAPH ISO-MORPHISM is easy. (Here, easy means takes polynomial time. )

However, canonical number may be harder than GRAPH ISOMORPHISM. If I can tell that two graphs are NOT isomorphic, I know that their canonical numbers are di↵erent, but I don’t know what their canonical numbers are. Further, if I know that two graphs are isomorphic, I know that their canonical numbers are identical, but again I don’t know what these canonical numbers are.

1. 2. Is-Canonical:

INPUT: A graph G and an integer I.

QUESTION: Is I < the canonical number of G?

EXERCISE: Show that IS-CANONICAL is in co-N P.

11. Tautology:

INPUT: A Boolean Expression E(x₁, . . . , x_n).

QUESTION: Does E evaluate to TRUE for each and every assignment of TRUE and FALSE to the variables, the x’s ?

Show that TAUTOLOGY is co-N P-complete.

12. 3-SAT:

INPUT: A Boolean Expression E(x₁, . . . , x_n) in Clause form with at most 3 literals per clause.

QUESTION: Does E evaluate to TRUE for some assignment of TRUE and FALSE to the variables, the x’s ?

Show that if SAT is N P-complete, then 3-SAT is N P-complete.