I am preparing for the qual now so I am going to write my answers to the previous qual questions here. That way my professors can see and critique my answers.
-----
Fall 2009 Part 1 - Problem 1:
CLAIM: The given problem can be reduced in polynomial time to the problem that is the same except that the paths are not required to have disjoint edges (only the nonterminal vertices are required to be disjoint.)
PROOF: Suppose we modify a given instance of the problem by stating that for each edge (A,B), we add a new non-terminal vertex C and replace the edge (A,B) with edges (A,C) and (C,B). Then for any path, each edge the path used in the original graph will correspond to a vertex that the path will use in the new graph. So then the condition of vertex disjointness will include the condition of edge disjointness.
(???)
----
Fall 2009 Part 1 - Problem 2
CLAIM 0: Given any collection of numbers A_i which can collectively be represented by X bits, their sum can be represented by at most X bits.
PROOF 0: Proof by induction on n, the number of numbers in the collection.
Base Case (n=1): Trivial, since the sum is just the number itself.
Inductive Case (from n=k, prove true for n=k+1): Let Y be the number of bits needed to represent A_1 through A_k. Then their sum also can be represented with Y bits.
If A_k+1 requires less than or equal to Y bits to represent, then it is at most 2^Y - 1, and since the sum of the others is also at most 2^Y - 1, the total sum is at most 2^(Y+1)-1 and can be represented in at most Y+1 bits. Since A_k+1 requires at least one bit to represent, X>=Y+1 and the statement holds
Suppose A_k+1 requires more than Y bits to represent. We know it requires X-Y bits. Then we have the sum of the others is also at most 2^(X-Y) - 1 (since that is greater than the bound of 2^Y-1) so the total sum is at most 2^(X-Y+1)-1 and can be represented in (X-Y+1) bits. Since Y must be at least 1, (X-Y+1) <=X and the statement holds.
CLAIM 1: If A can be represented by m bits and B can be represented by n bits, then AB can be represented by at most (m+n) bits.
PROOF 1: We must have abs(A) <= (2^m)-1, and abs(B) <= (2^n)-1, so we have abs(AB) = abs(A)*abs(B) <= (2^m)-1 * (2^n) -1 <= (2^(m+n))-1.
CLAIM 1.5: Given any collection of numbers A_1 through A_n which can collectively be represented by X bits, their product can be represented by at most X bits.
PROOF 1.5 (by induction on n)
Base Case(n=1): This is trivial, since the product of a single number is just the number itself.
Inductive Case (from n=k to n=k+1): Suppose that A_k+1 can be represented in Y bits. Then A_1 through A_k can collectively be represented in X-Y. So the product of A_1 through A_k can be represented in X-Y bits by the inductive hypothesis, and by Claim 1 the product of A_1 through A_k+1 can be represented in (X-Y)+Y = X bits.
CLAIM 2: An n*n matrix that can be represented in U bits has a determinant that can also be represented in U bits.
PROOF 2: Proof by induction on n.
Base Case (n=1): This is trivial, since the determinant of a 1x1 matrix is simply that matrix's single entry.
Inductive Case (from n=k, prove true for n=k+1): Consider a (k+1)x(k+1) matrix M. Let A be the number of bits required to express the entries in the first row; then U-A is the number of bits required to express the entries in the remainder of the matrix. Now consider the expansion of the determinant by minors using the first row of the matrix. We have:
(note: M(1,i) means the given entry of M, M{1,i} means the minor)
abs(det(M))
= abs(sum(i goes from 1 to k+1) of M(1,i) * (det(M{1,i}))
<= sum(i goes from 1 to k+1) of abs(M(1,i) * det(M{1,i}))
<= sum(i goes from 1 to k+1) of abs(M(1,i) * (2^(U-A)-1)) by the inductive hypothesis, since M{1,i} can be represented in at most U-A bits
= (2^(U-A)-1) * sum(i goes from 1 to k+1) of abs(M(1,i))
<= (2^(U-A)-1) * (2^A)-1 (by Claim 0, since all the M(1,i) can be represented in a total of A bits)
<= (2^U) - 1
So det(M) can be represented in U bits.
Since U is a polynomial in U, Part A of the problem holds.
For Part B, suppose that D is the total number of bits needed to store the denominators of the rational numbers, and thus U-D is the number of bits needed to store the numerators. Let k be the product of all the denominators. We know that k can be represented in at most D bits by Claim 1.5. Consider the matrix kM. We know kM is an integer matrix since we multiplied each value by a number that it is a multiple of its denominator. Also, the number of bits needed to store kM is at most (U-D)+((n^2)D) <= (U-D)+(UD) <= U^2. Thus by Part A the number of bits needed to store det(kM) is at most U^2. We know det(M) = det(kM)/(k^n), so the determinant of M can be stored with at most U^2 bits for the numerator plus no more than nD <= UD <= U^2 additional bits for the denominator, so the total number of bits is at most 2U^2, which is a polynomial in U.
For Part C:
Given an instance P = (A,c,b,K), consider the instance Q = (dA, dc, db, dK), where d is equal to the denominator of K, times all the denominators of the elements of A, times all the denominators of the elements of c, times all the denominators of the elements of b.
CLAIM 3: The instance Q can be represented in a number of bits polynomial in the number of bits required to represent P.
PROOF 3: Suppose P can be represented in A bits. Then since d is equal to the product of all the denominators, and since the denominators can be represented in less than or equal to A bits collectively, d can be represented in less than or equal to A bits. When you multiply each of the numbers d, you are adding at most A bits to the binary representation of each number, and there are (n^2+n+n+1) <= (4n^2) numbers. So the number of bits you end up with is at most A+(4n^2)A <= (5n^2)A <= (5A^2)A = 5A^3, which is polynomial in A.
CLAIM 4: All the numbers in Q are integers.
PROOF 4: Each number in Q is a rational number in P, multiplied by d, which is a multiple of its denominator.
(???)
--------
Fall 2009 Part 1 - Problem 3
Part A:
Proof by induction on n.
Base Case (n=1)
No comments:
Post a Comment