2011-12-10

Re: Practice Final Answers - Post your answers here .

'''Originally Posted By: jnewth'''

Problem 8: Show GNI is in IP. Addressed in page 148 of the book and the notes of November 30th. The problem is relevant because it is a problem in IP not known to be in NP. There is a great image of two isomorphic graphs and the permutation description at wikipedia: http://en.wikipedia.org/wiki/Graph_isomorphism Graph isomorphism (GI) GI, the problem of deciding if two graphs are isomorphs (ie, the nodes can be permuted without changing the edge structure to form the other graph) is in NP, because a certificate can be a description of the permutation. It is not known if GNI, that of declaring if two graphs are NOT isomorphic is in NP. It can however be stated as a problem in IP in the following way: V: Pick i=0/1. Randomly permute the vertices of graph i to get a new graph H. V: Send H to the prover P. P: Identify which graph G0 or G1 the H came from. If it could have come from either, guess which one. Send the guess j back to V. V: If i == j accept; else reject. If the graphs are not the same then there exists a prover that can tell them apart, or rather there exists P such that Pr(V accepts) = 1. This is greater than 2/3, so we meet the Completeness requirement for IP. If on the other hand the graphs are the same, the best that prover can do is guess G0 or G1, so in every case Pr[V accepts] jnewth &mdash; Sat Dec 10, 2011 6:46 pm <hr>

'''Originally Posted By: jnewth''' Problem 8: Show GNI is in IP. Addressed in page 148 of the book and the notes of November 30th. The problem is relevant because it is a problem in IP not known to be in NP. There is a great image of two isomorphic graphs and the permutation description at wikipedia: http://en.wikipedia.org/wiki/Graph_isomorphism Graph isomorphism (GI) GI, the problem of deciding if two graphs are isomorphs (ie, the nodes can be permuted without changing the edge structure to form the other graph) is in NP, because a certificate can be a description of the permutation. It is not known if GNI, that of declaring if two graphs are NOT isomorphic is in NP. It can however be stated as a problem in IP in the following way: V: Pick i=0/1. Randomly permute the vertices of graph i to get a new graph H. V: Send H to the prover P. P: Identify which graph G0 or G1 the H came from. If it could have come from either, guess which one. Send the guess j back to V. V: If i == j accept; else reject. If the graphs are not the same then there exists a prover that can tell them apart, or rather there exists P such that Pr(V accepts) = 1. This is greater than 2/3, so we meet the Completeness requirement for IP. If on the other hand the graphs are the same, the best that prover can do is guess G0 or G1, so in every case Pr[V accepts] jnewth — Sat Dec 10, 2011 6:46 pm <hr>

Practice Final Answers - Post your answers here

'''Originally Posted By: jnewth'''

Problem 7: Show BPP is in Sigma-P2. This proof is Sipser-Gacs presented pg 136 and the notes of November 28. Proof Idea: BPP is contained in the intersection of Sigma-P2 and Pi-P2 which can be simplified to Sigma-P2 because BPP=coBPP, i.e. BPP is closed under complementation. If x is the language L in BPP, then there is a certificate r that causes M to accept x with some high probability. If x is not in the language, then there are a small number of certificates that will cause M to accept x erroneously. The rest of this proof uses the concept of &quot;shifts&quot; to show that thinking about the the sizes of these two sets of certificates (that cause M to accept x either correctly or incorrectly) can be phrased as a computation in Sigma-P2. Math ensues: For a language in L in BPP: x&isin;L&rArr;Pr[M(x,r)accepts]&ge;1-2^-n x&notin;L&rArr;Pr[M(x,r)accepts]&le;2^-n For x of length n, Sx is the set of certificate &quot;r&quot; of length at most m for which M accepts . If x&isin;L then size Sx = Pr(M(x,r) accepts correctly) * number of strings of length m |Sx|&gt;=(1-2^-n)(2^m) And by similar reasoning for x&notin;L Sx = Pr(M(x, r) accepts erroneously) * number of strings of length m |Sx| Shift: If we have a set of strings of length m and a shift string u of length m, we shift S by u by doing bitwise addition of every string in S with u, creating a new set of strings of the same size as the original set S. We generate a new set for each shift. Claim 1: For every set S&sube;{0,1}^m with |S|&le;2^(m-n) and k vectors u1,...uk, the union of all strings for each shift Proof: The shift of the set has the same number of strings as the original set, so if we add all the shifted sets together, we would get at most k|S| total strings. k*|S| strings is less than 2^m, the total possible number of strings of length m. This is because m=|r| (ie the length of a certificate) which can only be polynomial in n. The algebra is in the notes. Claim 2: For every set S&sube;{0,1}^m with |S|&ge;(1-2^-n)*(2^m), there exist u1,...,uk such that the union of all shifted sets = {0,1}^m (IE A big enough set with k shifts CAN generate all 2^m strings of length m) We want to show that there is at least SOME choice of shifts for which this is true. We do this by showing Pr[there exists a string of length m that is not in S'] jnewth &mdash; Sat Dec 10, 2011 6:25 pm <hr>

'''Originally Posted By: jnewth''' Problem 7: Show BPP is in Sigma-P2. This proof is Sipser-Gacs presented pg 136 and the notes of November 28. Proof Idea: BPP is contained in the intersection of Sigma-P2 and Pi-P2 which can be simplified to Sigma-P2 because BPP=coBPP, i.e. BPP is closed under complementation. If x is the language L in BPP, then there is a certificate r that causes M to accept x with some high probability. If x is not in the language, then there are a small number of certificates that will cause M to accept x erroneously. The rest of this proof uses the concept of "shifts" to show that thinking about the the sizes of these two sets of certificates (that cause M to accept x either correctly or incorrectly) can be phrased as a computation in Sigma-P2. Math ensues: For a language in L in BPP: x∈L⇒Pr[M(x,r)accepts]≥1-2^-n x∉L⇒Pr[M(x,r)accepts]≤2^-n For x of length n, Sx is the set of certificate "r" of length at most m for which M accepts . If x∈L then size Sx = Pr(M(x,r) accepts correctly) * number of strings of length m |Sx|>=(1-2^-n)*(2^m) And by similar reasoning for x∉L Sx = Pr(M(x, r) accepts erroneously) * number of strings of length m |Sx| Shift: If we have a set of strings of length m and a shift string u of length m, we shift S by u by doing bitwise addition of every string in S with u, creating a new set of strings of the same size as the original set S. We generate a new set for each shift. Claim 1: For every set S&sube;{0,1}^m with |S|≤2^(m-n) and k vectors u1,...uk, the union of all strings for each shift Proof: The shift of the set has the same number of strings as the original set, so if we add all the shifted sets together, we would get at most k*|S| total strings. k*|S| strings is less than 2^m, the total possible number of strings of length m. This is because m=|r| (ie the length of a certificate) which can only be polynomial in n. The algebra is in the notes. Claim 2: For every set S&sube;{0,1}^m with |S|≥(1-2^-n)*(2^m), there exist u1,...,uk such that the union of all shifted sets = {0,1}^m (IE A big enough set with k shifts CAN generate all 2^m strings of length m) We want to show that there is at least SOME choice of shifts for which this is true. We do this by showing Pr[there exists a string of length m that is not in S'] jnewth — Sat Dec 10, 2011 6:25 pm <hr>

-- Practice Final Answers - Post your answers here

'''Originally Posted By: Nishant'''

Q-2) Give an NC circuit family whose member nth member, Cn, computes the parity of its n input bits. Sol:) The language PARITY ={x : x has an odd number of 1s} is in NC1. The circuit computing it has the form of a binary tree. The answer appears at the root; the left subtree computes the parity of the first |x| /2 bits and the right subtree computes the parity of the remaining bits. The gate at the top computes the parity of these two bits. Clearly, unwrapping the recursion implicit in our description gives a circuit of depth O(log n). It is also logspace uniform.

'''Originally Posted By: Nishant''' Q-2) Give an NC circuit family whose member nth member, Cn, computes the parity of its n input bits. Sol:) The language PARITY ={x : x has an odd number of 1s} is in NC1. The circuit computing it has the form of a binary tree. The answer appears at the root; the left subtree computes the parity of the first |x| /2 bits and the right subtree computes the parity of the remaining bits. The gate at the top computes the parity of these two bits. Clearly, unwrapping the recursion implicit in our description gives a circuit of depth O(log n). It is also logspace uniform.

2011-12-13

-- Practice Final Answers - Post your answers here

'''Originally Posted By: cwong'''

-- Practice Final Answers - Post your answers here

'''Originally Posted By: Jay_Reynolds_Freeman'''

Problem 5 -- submitted by Jay Freeman: Give the randomized p-time algorithm for 2SAT and explain how its running time is determined. This matter is described in the lecture of 23 November, slides 3 through 5. The basic idea is to start with any (random) assignment of variables and repeat the following N times: If the formula is satisfied emit &quot;Satisfied&quot; Else take any unsatisfied clause, and flip one of its literals (randomly chosen) After N repetitions, emit, &quot;Probably not satisfiable.&quot; The key is to pick the number of literals to get a decent probability of finding a satisfying combination of literal assignments, if indeed there is one. For 2SAT, it turns out that N = 2 * n**2, where n is the number of literals, will make that probability 0.5. The proof involves setting up recurrence relations in t(i), the expected number of &quot;flip&quot; steps to obtain a solution when we start with i literals incorrect. t(0) = 0 (of course), t( i ) Jay_Reynolds_Freeman &mdash; Tue Dec 13, 2011 2:31 am <hr>

'''Originally Posted By: Jay_Reynolds_Freeman''' Problem 5 -- submitted by Jay Freeman: Give the randomized p-time algorithm for 2SAT and explain how its running time is determined. This matter is described in the lecture of 23 November, slides 3 through 5. The basic idea is to start with any (random) assignment of variables and repeat the following N times: If the formula is satisfied emit "Satisfied" Else take any unsatisfied clause, and flip one of its literals (randomly chosen) After N repetitions, emit, "Probably not satisfiable." The key is to pick the number of literals to get a decent probability of finding a satisfying combination of literal assignments, if indeed there is one. For 2SAT, it turns out that N = 2 * n**2, where n is the number of literals, will make that probability 0.5. The proof involves setting up recurrence relations in t(i), the expected number of "flip" steps to obtain a solution when we start with i literals incorrect. t(0) = 0 (of course), t( i ) Jay_Reynolds_Freeman — Tue Dec 13, 2011 2:31 am <hr>

-- Practice Final Answers - Post your answers here

'''Originally Posted By: stang'''

Question #3: Consider the language {a,k,a_1,...a_n|a is the k-th smallest a_i}. Show this is in BPP. Answer: By using the proof given in the class notes (Nov 21) about PTM, we can say that finding the k-th smallest number can be simulated on PTMs. After finding the k-th smallest element, we can verify it with given a in the question #3. Since BPP is the language that is declared by the class of language decided by PTM(s) in O(T(n)) time, hence BPP = U_c BPTIME(n^c). Thus, with the proofs from both, the language is in BPP.

'''Originally Posted By: stang''' Question #3: Consider the language {〈a,k,〈a_1,...a_n〉〉|a is the k-th smallest a_i}. Show this is in BPP. Answer: By using the proof given in the class notes (Nov 21) about PTM, we can say that finding the k-th smallest number can be simulated on PTMs. After finding the k-th smallest element, we can verify it with given a in the question #3. Since BPP is the language that is declared by the class of language decided by PTM(s) in O(T(n)) time, hence BPP = U_c BPTIME(n^c). Thus, with the proofs from both, the language is in BPP.

-- Practice Final Answers - Post your answers here

'''Originally Posted By: sctice'''

I apologize for posting this so late in the game. I'm not sure whether I was supposed to do 4 or 6, so I'll start with 4. Question 4: State Markov's Theorem and prove it. I'm assuming this question is referring to Markov's inequality, which is defined and proven here: http://www.cs.sjsu.edu/faculty/pollett/ ... ml#%285%29. I'll go ahead and write it out. The theorem says that any nonnegative random variable X satisfies Pr(X &gt;= k * E[X]) http://saravananthirumuruganathan.wordp ... qualities/. Question 6: State Chernoff bounds. Chernoff bounds are defined (and proved on the following slide) here: http://www.cs.sjsu.edu/faculty/pollett/ ... ml#%288%29. The bounds are useful (among other reasons) because they provide guarantees on error reduction for repeated trials, even when (as with BPP) both false positives and false negatives are possible.

'''Originally Posted By: sctice''' I apologize for posting this so late in the game. I'm not sure whether I was supposed to do 4 or 6, so I'll start with 4. Question 4: State Markov's Theorem and prove it. I'm assuming this question is referring to Markov's inequality, which is defined and proven here: http://www.cs.sjsu.edu/faculty/pollett/ ... ml#%285%29. I'll go ahead and write it out. The theorem says that any nonnegative random variable X satisfies Pr(X >= k * E[X]) http://saravananthirumuruganathan.wordp ... qualities/. Question 6: State Chernoff bounds. Chernoff bounds are defined (and proved on the following slide) here: http://www.cs.sjsu.edu/faculty/pollett/ ... ml#%288%29. The bounds are useful (among other reasons) because they provide guarantees on error reduction for repeated trials, even when (as with BPP) both false positives and false negatives are possible.

Query Statistics

https://yioop.com/thread/3313

Total Elapsed Time for Queries: 0.04296207427978516 seconds.

SELECT LOCALE_NAME, WRITING_MODE FROM LOCALE WHERE LOCALE_TAG ='en-US'

Time: 0.0001609325408935547 seconds.

SELECT COALESCE(MAX(UPDATE_TIMESTAMP), 0) AS MOST_RECENT FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID = 2 AND ITEM_TYPE = 3 AND ITEM_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = 2 AND STATUS = 1) AND UPDATE_PERIOD = -4

Time: 0.00037384033203125 seconds.

DELETE FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 3313 [2] => 1 )

Time: 0.003468036651611328 seconds.

INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES (?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 3313 [2] => 1 [3] => 1789983507 )

Time: 0.002187967300415039 seconds.

UPDATE ITEM_IMPRESSION_SUMMARY SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2 AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 3313 [2] => 1 )

Time: 0.0001018047332763672 seconds.

DELETE FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 247 [2] => 3 )

Time: 0.002132892608642578 seconds.

INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES (?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 247 [2] => 3 [3] => 1789983507 )

Time: 0.002160072326660156 seconds.

UPDATE ITEM_IMPRESSION_SUMMARY SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2 AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 247 [2] => 3 )

Time: 7.200241088867188E-5 seconds.

SELECT COUNT(GI.ID) AS NUM FROM GROUP_ITEM GI WHERE GI.GROUP_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = ? AND STATUS = 1) AND GI.TITLE NOT LIKE ? AND GI.PUBDATE > ?
Array ( [0] => 2 [1] => %2% [2] => 1789983498 )

Time: 0.0002899169921875 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-4 )

Time: 9.512901306152344E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-37 )

Time: 3.910064697265625E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-202 )

Time: 3.290176391601562E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-687 )

Time: 3.099441528320312E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1115 )

Time: 4.315376281738281E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1138 )

Time: 5.412101745605469E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1140 )

Time: 3.290176391601562E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1149 )

Time: 3.194808959960938E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1152 )

Time: 3.099441528320312E-5 seconds.

SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3313 )

Time: 0.0002360343933105469 seconds.