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

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

2021-04-15T00:25:20Z

Jittat เมื่อ 22:56, 14 เมษายน 2564

2021-04-14T22:56:54Z

Jittat เมื่อ 22:56, 14 เมษายน 2564

2021-04-14T22:56:04Z

Jittat เมื่อ 16:17, 17 มีนาคม 2564

2021-03-17T16:17:08Z

Jittat เมื่อ 15:50, 17 มีนาคม 2564

2021-03-17T15:50:25Z

Jittat เมื่อ 15:49, 17 มีนาคม 2564

2021-03-17T15:49:07Z

Jittat เมื่อ 15:48, 17 มีนาคม 2564

2021-03-17T15:48:21Z

Jittat เมื่อ 15:47, 17 มีนาคม 2564

2021-03-17T15:47:24Z

Jittat เมื่อ 15:25, 17 มีนาคม 2564

2021-03-17T15:25:32Z

Jittat เมื่อ 15:05, 17 มีนาคม 2564

2021-03-17T15:05:49Z

@@ แถว 18: / แถว 18: @@
 (b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>
 : ''Links:'' [[Computational complexity/hw2|การบ้าน 2]]
 [[Category:complexity]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 22:56, 14 เมษายน 2564
แถว 19:		แถว 19:
	(b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>		(b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>

−	: Links: [[Computational complexity/hw2\|การบ้าน 2]]	+	: ''Links:'' [[Computational complexity/hw2\|การบ้าน 2]]
		+
		+	[[Category:complexity]]

@@ แถว 1: / แถว 1: @@
-การบ้าน 1 มี xx ข้อ
+การบ้าน 1 มี 6 ข้อ
 . (AB-1.7) Define a ''two-dimensional'' Turing machine to be a TM where each of its tapes is an infinite grid (and the machine can move not only <tt>L</tt>eft and <tt>R</tt>ight, but also <tt>U</tt>p and <tt>D</tt>own).  Show that for every (time-constructible) <math>T:{\mathbb N}\rightarrow {\mathbb N}</math> and every Boolean function <math>f</math>, if <math>f</math> can be computed in time <math>T(n)</math> using a two-dimensional  TM then <math>f\in DTIME(T(n)^2)</math>.
@@ แถว 18: / แถว 18: @@
 (b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>

@@ แถว 9: / แถว 9: @@
 . (AB-2.23) Prove that <math>\mathbf{P}\subseteq \mathbf{NP}\cap\mathbf{coNP}</math>
-. (AB-6.8) A language <math>L\subseteq\{0,1\}^*</math> is sparse if there is a polynomial <math>p</math> such that <math>|L\cup\{0,1\}^n|\leq p(n)</math> for every <math>n\in{\mathbb N}</math>.  Show that every sparse language is in <math>\mathbf{P}_\mathrm{/poly}</math>.
+. (AB-6.8) A language <math>L\subseteq\{0,1\}^*</math> is sparse if there is a polynomial <math>p</math> such that <math>|L\cap\{0,1\}^n|\leq p(n)</math> for every <math>n\in{\mathbb N}</math>.  Show that every sparse language is in <math>\mathbf{P}_\mathrm{/poly}</math>.
 . (AB-7.5) Recall that, in lecture, we briefly state that one can simulate a coin with head probability <math>p</math>, if the real number <math>p</math> is efficiently computable.  Let us study to what extent this claim truly needs the assumption that <math>p</math> is efficiently computable.   Describe a real number <math>p</math> such that given a random coin that comes up "Heads" with probability <math>p</math>, a Turing machine can decide an undecidable language in polynomial time.

@@ แถว 11: / แถว 11: @@
 . (AB-6.8) A language <math>L\subseteq\{0,1\}^*</math> is sparse if there is a polynomial <math>p</math> such that <math>|L\cup\{0,1\}^n|\leq p(n)</math> for every <math>n\in{\mathbb N}</math>.  Show that every sparse language is in <math>\mathbf{P}_\mathrm{/poly}</math>.
-. (AB-7.6) (a) Prove that a language <math>L</math> is in <math>\mathbf{ZPP}</math> iff there exists a polynomial-time PTM <math>M</math> with output in <math>\{0,1,?\}</math> such that for every <math>x\in\{0,1\}^*</math>, with probability 1, <math>M(x)\in\{L(x),?\}</math> and <math>\mathbf{Pr}[M(x)=?]\leq 1/2</math>.
+. (AB-7.5) Recall that, in lecture, we briefly state that one can simulate a coin with head probability <math>p</math>, if the real number <math>p</math> is efficiently computable.  Let us study to what extent this claim truly needs the assumption that <math>p</math> is efficiently computable.   Describe a real number <math>p</math> such that given a random coin that comes up "Heads" with probability <math>p</math>, a Turing machine can decide an undecidable language in polynomial time.
-(b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>
+: ''Hint:'' Think of the real number <math>p</math> as an advice string.  How can its bits be recovered?
-. (AB-7.5) Recall that, in lecture, we briefly state that one can simulate a coin with head probability <math>p</math>, if the real number <math>p</math> is efficiently computable.  Let us study to what extent this claim truly needs the assumption that <math>p</math> is efficiently computable.   Describe a real number <math>p</math> such that given a random coin that comes up "Heads" with probability <math>p</math>, a Turing machine can decide an undecidable language in polynomial time.
+. (AB-7.6) (a) Prove that a language <math>L</math> is in <math>\mathbf{ZPP}</math> iff there exists a polynomial-time PTM <math>M</math> with output in <math>\{0,1,?\}</math> such that for every <math>x\in\{0,1\}^*</math>, with probability 1, <math>M(x)\in\{L(x),?\}</math> and <math>\mathbf{Pr}[M(x)=?]\leq 1/2</math>.
-: ''Hint:'' Think of the real number <math>p</math> as an advice string.  How can its bits be recovered?
+(b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>

@@ แถว 5: / แถว 5: @@
 . (AB-2.17, 1st half) In the '''Exactly One 3SAT''' problem, we are given a 3CNF formula <math>\phi</math> and need to decide if there exists a satisfying assignment <math>u</math> for <math>\phi</math> such that every clause of <math>\phi</math> has exactly one True literal.  Prove that '''Exactly One 3SAT''' is '''NP'''-complete.
-: ''Hint:'' Replace each occurrence of a literal <math>v_i</math> in a clause <math>C</math> by a new variable <math>z_{i,C}</math> with auxiliary variables ensuring that if <math>v_i</math> is TRUE, then <math>z_{i,C}</math> can be either TRUE or FALSE, but if <math>v_i</math> is FALSE, then <math>z_{i,C}</math> must be FALSE.
+: ''Hint:'' Replace each occurrence of a literal <math>v_i</math> in a clause <math>C</math> by a new variable <math>z_{i,C}</math> with additional clauses and auxiliary variables ensuring that if <math>v_i</math> is TRUE, then <math>z_{i,C}</math> can be either TRUE or FALSE, but if <math>v_i</math> is FALSE, then <math>z_{i,C}</math> must be FALSE.
 . (AB-2.23) Prove that <math>\mathbf{P}\subseteq \mathbf{NP}\cap\mathbf{coNP}</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:47, 17 มีนาคม 2564
แถว 10:		แถว 10:

	4. (AB-6.8) A language <math>L\subseteq\{0,1\}^*</math> is sparse if there is a polynomial <math>p</math> such that <math>\|L\cup\{0,1\}^n\|\leq p(n)</math> for every <math>n\in{\mathbb N}</math>. Show that every sparse language is in <math>\mathbf{P}_\mathrm{/poly}</math>.		4. (AB-6.8) A language <math>L\subseteq\{0,1\}^*</math> is sparse if there is a polynomial <math>p</math> such that <math>\|L\cup\{0,1\}^n\|\leq p(n)</math> for every <math>n\in{\mathbb N}</math>. Show that every sparse language is in <math>\mathbf{P}_\mathrm{/poly}</math>.
		+
		+	5. (AB-7.6) (a) Prove that a language <math>L</math> is in <math>\mathbf{ZPP}</math> iff there exists a polynomial-time PTM <math>M</math> with output in <math>\{0,1,?\}</math> such that for every <math>x\in\{0,1\}^*</math>, with probability 1, <math>M(x)\in\{L(x),?\}</math> and <math>\mathbf{Pr}[M(x)=?]\leq 1/2</math>.
		+
		+	(b) Show that <math>\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{coRP}</math>
		+
		+	6. (AB-7.5) Recall that, in lecture, we briefly state that one can simulate a coin with head probability <math>p</math>, if the real number <math>p</math> is efficiently computable. Let us study to what extent this claim truly needs the assumption that <math>p</math> is efficiently computable. Describe a real number <math>p</math> such that given a random coin that comes up "Heads" with probability <math>p</math>, a Turing machine can decide an undecidable language in polynomial time.
		+
		+	: ''Hint:'' Think of the real number <math>p</math> as an advice string. How can its bits be recovered?

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:05, 17 มีนาคม 2564
แถว 1:		แถว 1:
	การบ้าน 1 มี xx ข้อ		การบ้าน 1 มี xx ข้อ

−	1 (1.7) Define a ''two-dimensional'' Turing machine to be a TM where each of its tapes is an infinite grid (and the machine can move not only <tt>L</tt>eft and <tt>R</tt>ight, but also <tt>U</tt>p and <tt>D</tt>own). Show that for every (time-constructible) <math>T:N\rightarrow N</math> and every Boolean function <math>f</math>, if <math>f</math> can be computed in time <math>T(n)</math> using a two-dimensional TM then <math>f\in DTIME(T(n)^2)</math>.	+	1. (AB-1.7) Define a ''two-dimensional'' Turing machine to be a TM where each of its tapes is an infinite grid (and the machine can move not only <tt>L</tt>eft and <tt>R</tt>ight, but also <tt>U</tt>p and <tt>D</tt>own). Show that for every (time-constructible) <math>T:N\rightarrow N</math> and every Boolean function <math>f</math>, if <math>f</math> can be computed in time <math>T(n)</math> using a two-dimensional TM then <math>f\in DTIME(T(n)^2)</math>.
		+
		+	2. (AB-2.17, 1st half) In the '''Exactly One 3SAT''' problem, we are given a 3CNF formula <math>\phi</math> and need to decide if there exists a satisfying assignment <math>u</math> for <math>\phi</math> such that every clause of <math>\phi</math> has exactly one True literal. Prove that '''Exactly One 3SAT''' is '''NP'''-complete.
		+
		+	: ''Hint:'' Replace each occurrence of a literal <math>v_i</math> in a clause <math>C</math> by a new variable <math>z_{i,C}</math> with auxiliary variables ensuring of <math>v_i</math> is TRUE, then <math>z_{i,C}</math> can be either TRUE or FALSE, but if <math>v_i</math> is FALSE, then <math>z_{i,C}</math> must be FALSE.
		+
		+	3. (AB-2.23) Prove that <math>\mathbf{P}\subseteq \mathbf{NP}\cap\mathbf{coNP}</math>