Computational complexity/hw2 - ประวัติรุ่นแก้ไข

Jittat เมื่อ 01:15, 15 เมษายน 2564

2021-04-15T01:15:18Z

2021-04-15T00:30:19Z

2021-04-15T00:29:39Z

2021-04-15T00:23:59Z

2021-04-15T00:22:15Z

2021-04-15T00:21:29Z

2021-04-15T00:10:50Z

2021-04-15T00:02:31Z

2021-04-14T22:57:47Z

สร้างหน้าด้วย "การบ้าน 2 มี xx ข้อ 1. : ''Links:'' การบ้าน 1 Category:complexity"

หน้าใหม่

การบ้าน 2 มี xx ข้อ

1.

: ''Links:'' [[Computational complexity/hw1|การบ้าน 1]]

[[Category:complexity]]

@@ แถว 19: / แถว 19: @@
 . (optional) (AB-3.2) Show that <math>\mathrm{SPACE}(n)\neq \mathbf{NP}</math>.  (Note that we do not know if either class is contained in the other.)
-: ''Hint:'' See first answer in [https://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56266 mathoverflow].  Also this [https://www.scottaaronson.com/blog/?p=392 blog post on Sidesplitting proofs].
+: ''Hint:'' See first answers in [https://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56266 mathoverflow] (and more hints at [https://cs.stackexchange.com/questions/93434/show-that-np-is-not-equal-to-spacen here]).  Also this [https://www.scottaaronson.com/blog/?p=392 blog post on Sidesplitting proofs].
 . (optional) (AB-8.1-c) Let <math>\mathbf{IP}'</math> denote the class obtained by changing the constant 2/3 in the completeness part of the definition of <math>\mathbf{IP}</math> to 1.  Prove that <math>\mathbf{IP}' = \mathbf{IP}</math>.

@@ แถว 11: / แถว 11: @@
 . (AB-9.5) Show that if <math>\mathbf{P} = \mathbf{NP}</math>, then one-way functions do not exist.
-. Consider random variables <math>Z_1,Z_2,\ldots,Z_n</math> and let random variable <math>Z=\sum_{i=1}^n Z_i</math>.  We know that when <math>Z_i</math>'s are independent, <math>\mathrm{Var}(Z)=\sum_{i=1}^n \mathrm{Var}(Z_i)</math>.  Show that the equality still holds when <math>Z_i</math>'s are only pair-wise independent.
+. (AB-9.11) Show that if <math>f</math> is a one-way permutation then so is <math>f^k</math> (which is <math>f</math> applied <math>k</math> times), where <math>k=n^c</math> for some fixed <math>c>0</math>.
 : ''Hint:'' Use the definition of variance.
 . (optional) (AB-3.2) Show that <math>\mathrm{SPACE}(n)\neq \mathbf{NP}</math>.  (Note that we do not know if either class is contained in the other.)

@@ แถว 1: / แถว 1: @@
-การบ้าน 2 มี 8 ข้อ (optional 2 ข้อ)
+การบ้าน 2 มี 9 ข้อ (optional 2 ข้อ)
 . (AB-4.5) Prove that <math>\mathrm{2SAT}</math> is in <math>\mathbf{NL}</math>.
@@ แถว 15: / แถว 15: @@
 : ''Hint:'' Use the definition of variance.
-. (optional) (AB-3.2) Show that <math>\mathrm{SPACE}(n)\neq \mathbf{NP}</math>.  (Note that we do not know if either class is contained in the other.)
+. Show that if <math>f</math> is a one-way permutation then so is <math>f^k</math> (which is <math>f</math> applied <math>k</math> times), where <math>k=n^c</math> for some fixed <math>c>0</math>.
 : ''Hint:'' See first answer in [https://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56266 mathoverflow].  Also this [https://www.scottaaronson.com/blog/?p=392 blog post on Sidesplitting proofs].
 . (optional) (AB-8.1-c) Let <math>\mathbf{IP}'</math> denote the class obtained by changing the constant 2/3 in the completeness part of the definition of <math>\mathbf{IP}</math> to 1.  Prove that <math>\mathbf{IP}' = \mathbf{IP}</math>.
 : ''Hint:'' Use <math>\mathbf{IP} = \mathbf{PSPACE}</math>.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 00:23, 15 เมษายน 2564
แถว 1:		แถว 1:
−	การบ้าน 2 มี xx ข้อ	+	การบ้าน 2 มี 8 ข้อ (optional 2 ข้อ)

	1. (AB-4.5) Prove that <math>\mathrm{2SAT}</math> is in <math>\mathbf{NL}</math>.		1. (AB-4.5) Prove that <math>\mathrm{2SAT}</math> is in <math>\mathbf{NL}</math>.

@@ แถว 17: / แถว 17: @@
 . (optional) (AB-3.2) Show that <math>\mathrm{SPACE}(n)\neq \mathbf{NP}</math>.  (Note that we do not know if either class is contained in the other.)
-: ''Hint:'' See first answer in [https://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56266 mathoverflow].
+: ''Hint:'' See first answer in [https://mathoverflow.net/questions/56265/np-not-equal-to-spacen/56266 mathoverflow].  Also this [https://www.scottaaronson.com/blog/?p=392 blog post on Sidesplitting proofs].
 . (optional) (AB-8.1-c) Let <math>\mathbf{IP}'</math> denote the class obtained by changing the constant 2/3 in the completeness part of the definition of <math>\mathbf{IP}</math> to 1.  Prove that <math>\mathbf{IP}' = \mathbf{IP}</math>.

@@ แถว 9: / แถว 9: @@
 . (AB-8.1-d) Let <math>\mathbf{IP}'</math> denote the class obtained by changing the constant 1/3 in the soundness part of the definition of <math>\mathbf{IP}</math> to 0.  Prove that <math>\mathbf{IP}' = \mathbf{NP}</math>.
-. (AB-8.1-c) (optional) Let <math>\mathbf{IP}'</math> denote the class obtained by changing the constant 2/3 in the completeness part of the definition of <math>\mathbf{IP}</math> to 1.  Prove that <math>\mathbf{IP}' = \mathbf{IP}</math>.
+. (AB-9.5) Show that if <math>\mathbf{P} = \mathbf{NP}</math>, then one-way functions do not exist.
 : ''Links:'' [[Computational complexity/hw1|การบ้าน 1]]
 [[Category:complexity]]