Description

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.

Show that MULTIPLICATION SQUARING.

Show that SQUARING MULTIPLICATION.

Show that SQUARING RECIPROCAL.

If A ⌘ B means A B and B A which of MULTIPLICATION, SQUARING, and RECIPROCAL are equivalent ?
HINT: _{x}^{1} − _{y}^{1} = ^{y}_{x}^{−}_{y}^{x} . Try y = x + 1.

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_{0} = 2, L_{1} = 1 Show that this problem is in P by outlining (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.

Roots:
Without finding the solutions, show that x^{2} − x − 1 = 0 has:


NO positive integer solutions



NO rational solutions

HINTS:



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





p^{2} − q^{2} = (p − q) (p + q).





Each integer is either ODD or EVEN.



Average Case:
Do Exercise 5.25 in the NOTES on page 61.

Lower Bound:
Exercise 6.1 in the NOTES on page 71, is about the lower bound of ^{3}_{2} n − 2 comparisons to find the largest and smallest elements in an array. Devise a divideandconquer algorithm for this problem and show that the number of comparisons used by your algorithm achieves this lower bound.
Assume that you have an algorithm YS( ) so that when you input a Boolean expression E(x_{1}, . . . , x_{n}) into YS( ) ,
YS( E ) outputs YES if E is satisfiable, and YS( E ) outputs NO if E is not satisfiable.


Show how to use YS( ) to construct an algorithm FIND( D(x_{1}, . . . , x_{n})) which when given a satisfiable Boolean expression D(x_{1}, . . . , x_{n}), returns an assignment x_{1} = a_{1}, x_{2} = a_{2}, . . . , x_{n} = a_{n}, so that D(a_{1}, . . . , a_{n}) is TRUE.



Assume that YS( D(x_{1}, . . . , x_{n}) ) has run time O( n^{k} ) and find the run time of FIND( D(x_{1}, . . . , x_{n}) ) .


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

st 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?


Assume that you know that Hamiltonian Circuit is N P −Complete, show that st Hamiltonian Path is N P −Complete.



Assume that you know that st Hamiltonian Path is N P −Complete, show that Hamiltonian Circuit is N P −Complete.



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 Circuit is N P −Complete.)


Graph Isomorphism:
Graph isomorphism is an example of a problem which is in N P, but is not known to be N Pcomplete, nor is it known to be in coN P.
INPUT: Two graphs, G_{1} = (V_{1} , E_{1}) and G_{2} = (V_{2} , E_{2}).
QUESTION: Can the vertices of G_{1} be renamed so that G_{1} becomes G_{2}? (Is there a
onetoone onto function f : V_{1} ! V_{2} so that 8x, y (x, y) 2 E_{1} i↵( f(x), f(y) ) 2 E_{2}? Show that GRAPH ISOMORPHISM is in N P.
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^{2} 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^{2} bit numbers. If we relabel the vertices of the graph, we don’t change the graph properties. Di↵erent relabelings of the graph will (usually) give di↵erent numbers. Clearly among all relabelings of the graph, there is some relabeling which gives the smallest value for this binary number. We would like to represent a graph by the minimum number we can get by relabeling. 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_{1} — v_{2} — v_{3} is isomorphic to v_{1} — v_{3} — v_{2} and is also isomorphic to v_{2} — v_{1} — v_{3}.
Find the canonical number of v_{1} — v_{2} — v_{3}.


Show that if finding the canonical number of a graph is easy, then GRAPH ISOMORPHISM 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.


IsCanonical:

INPUT: A graph G and an integer I.
QUESTION: Is I < the canonical number of G?
EXERCISE: Show that ISCANONICAL is in coN P.

Tautology:
INPUT: A Boolean Expression E(x_{1}, . . . , 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 coN Pcomplete.

3SAT:
INPUT: A Boolean Expression E(x_{1}, . . . , 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 Pcomplete, then 3SAT is N Pcomplete.