Homework #8 Reductions

CS 325

Homework #8
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.
(a) Show that MULTIPLICATION  SQUARING.
(b) Show that SQUARING  MULTIPLICATION.
(c) Show that SQUARING  RECIPROCAL.
(d) If A ⌘ B means A  B and B  A which of MULTIPLICATION, SQUARING, and RECIPROCAL are equivalent ?
HINT: 1
x 1
y = y x
x y . 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 = Ln1 + L n2
with the initial conditions: L0 = 2, L1 = 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.
3. Roots:
Without finding the solutions, show that x2 x 1 = 0 has:
(a) NO positive integer solutions
(b) NO rational solutions
HINTS:
i. Assume that x = p/q where p and q are integers with no common factors.
ii. p2 q2 = (p q) (p + q).
iii. Each integer is either ODD or EVEN.
4. Average Case:
Do Exercise 5.5 in the NOTES on page 61.
5. 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 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(x1,...,xn) into YS( ) ,
YS( E ) outputs YES if E is satisfiable, and
YS( E ) outputs NO if E is not satisfiable.
(a) Show how to use YS( ) to construct an algorithm FIND( D(x1,...,xn)) which
when given a satisfiable Boolean expression D(x1,...,xn), returns an assignment
x1 = a1, x2 = a2, ..., xn = an, so that D(a1,...,an) is TRUE.
(b) Assume that YS( D(x1,...,xn) ) has run time O( nk ) and find the run time of
FIND( D(x1,...,xn) ) .
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?
(a) Assume that you know that Hamiltonian Circuit is N PComplete, show that s-t
Hamiltonian Path is N PComplete.
(b) Assume that you know that s-t Hamiltonian Path is N PComplete, show that
Hamiltonian Circuit is N PComplete.
(c) Show that the Yes/No version of TSP (Traveling Sales Person) with all edge
weights in {1, 2} is N PComplete. (You should assume that Hamiltonian Circuit is N PComplete.)
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, G1 = (V1 , E1) and G2 = (V2 , E2).
QUESTION: Can the vertices of G1 be renamed so that G1 becomes G2? (Is there a
one-to-one onto function f : V1 ! V2 so that 8x, y (x, y) 2 E1 i↵ ( f(x), f(y) ) 2 E2?
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 (vi, vj ). If you “unroll” this matrix
(say by rows), you will have a vector of n2 bits and you can consider this to be a
number in standard binary notation. So, there is a correspondence between n vertex
graphs and n2 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 v1 — v2 — v3 is isomorphic to v1 — v3 — v2 and is also isomorphic to
v2 — v1 — v3.
Find the canonical number of v1 — v2 — v3.
(b) 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.
(c) 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(x1,...,xn).
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(x1,...,xn) 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.