Starting from:
$24
Homework #8 Solution
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, SQUAR-ING, and RECIPROCAL are equivalent ?
HINT: x1 − y1 = yx−yx . 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: L0 = 2, L1 = 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.
Roots:
Without finding the solutions, show that x2 − 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.
p2 − q2 = (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 32 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.
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.
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.
Assume that YS( D(x1, . . . , xn) ) has run time O( nk ) and find the run time of FIND( D(x1, . . . , xn) ) .
Platonic Hamiltonian Circiuts:
Show that each of the PLATONIC solids has a Hamiltonian circuit.
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?
Assume that you know that Hamiltonian Circuit is N P −Complete, show that s-t Hamiltonian Path is N P −Complete.
Assume that you know that s-t 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 Cir-cuit 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 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.
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.
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.
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.
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.
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.
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, SQUAR-ING, and RECIPROCAL are equivalent ?
HINT: x1 − y1 = yx−yx . 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: L0 = 2, L1 = 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.
Roots:
Without finding the solutions, show that x2 − 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.
p2 − q2 = (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 32 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.
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.
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.
Assume that YS( D(x1, . . . , xn) ) has run time O( nk ) and find the run time of FIND( D(x1, . . . , xn) ) .
Platonic Hamiltonian Circiuts:
Show that each of the PLATONIC solids has a Hamiltonian circuit.
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?
Assume that you know that Hamiltonian Circuit is N P −Complete, show that s-t Hamiltonian Path is N P −Complete.
Assume that you know that s-t 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 Cir-cuit 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 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.
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.
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.
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.
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.
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.
1 file (10.9MB)
