Whiteboard for the discussion session
- CS 332 - Elements of the Theory of Computation [Spring 2013] - Peter Gacs
Course Page: http://www.cs.bu.edu/faculty/gacs/courses/cs332/Home.html
Lab Hours: Mon 12-1, 1-2, 4-5, MCS B33
Coordinates: MCS 136
Email: at the right bottom of this page
Office Hours: Tue 9:00 - 10:30, Thu 14:00 - 15:30
Lab Hours: Mon 12-1, 1-2, 4-5, MCS B33
Coordinates: MCS 136
Email: at the right bottom of this page
Office Hours: Tue 9:00 - 10:30, Thu 14:00 - 15:30
Notes 01 - Jan. 28
Intro to Computation models, Turing Machine. For your reference: Circuit and Finite Automata.
Notes 02 - Feb. 4
Understanding Turing Machine and Transition Table, Cellular Automaton. Game of life, FYI
An Turing Machine Simulator
Notes 03 - Feb. 11
Handling Universal Turing Machine. Summary of computation models
Undecidability of the spectral gap
Notes 04 - Feb. 20 (WED, subst. Feb. 18)
A survey over the cost of basic arithmetic and integer factoring, see this [section 3-5] and this.
Notes 05 - Feb. 25
The P vs NP poll, FYI
Definition of P and NP:
Polynomial-time solvable language L: for all x in L, a machine M running in time polynomial to the length of |x|
NP language L: for all x in L, given a witness w (|w|=polysize(|x|)), M(x,w)->1, running in polytime.
Examples of NP problems:
Integer Factoring (in both NP and CoNP),
PATH (Given a graph and two points, find a path from A to B, in P, using BFS or DFS, in Polytime),
CYCLE (Given a graph, decide whether there's a CYCLE in the graph, in P),
Independent set (Given a graph G with N nodes, a number k<=N, decide whether there's a set of nodes with size >=k, that no edges between each pair of nodes),
CLIQUE (Complement of INDSET)
Notes 06 - Mar. 4
Polynomial-time-reduction, examples:
INDSET<->CLIQUE:
Given an instance x (a graph G<n,k>) in INDSET, pick the complement of G: G' (put edges on where there's no edges on the original graph G, so that if there's a CLIQUE in G'<n,k>, there's an INDSET in G<n,k>)
SubsetSum->0-1 Programming
Notes 07 - Mar. 18
Cont. (map of) Karp reductions, proof of NP-completeness.
Reducing CLIQUE <n,k> to CLIQUE<2n,n>: add n nodes in the original G, pick n-k of them and connecting with every other nodes in the graph.
Notes 08 - Mar. 25
Mid-term review, direction of reduction
Notes 09 - Apr. 01 - A good day to talk about undecidability!
Recap: constructive way of proving there are some language/function:"UC" that is uncomputable.
Reduce UC to the undecidability of HALTING problem.
An example: if the HALTING problem is decidable, then we can prove/disprove Goldbach's Conjecture
Hint of problem 1, problem 3 in HW7
Problem 1: Enumerating all the strings wa, wb, ... in the set of alphabet, using the UTM to decide whether Mi could decide wj, if not, ...
Problem 3: Reducing HALTING problem to this problem. You may like to take reference from http://www.cs.bu.edu/~gacs/papers/Lovasz-notes.pdf, Corollary 3.1.3.
Notes 10 - Apr. 08
Review of Undecidability, prove of undecidability: the set of <M>s that M always halts on some given input string 'a' (including empty input tape) is undecidable.
Notes 11 - Apr. 18 (THU, subst. Apr. 15)
Review the reduction from 3SAT to 0-1 PROG, to SUBSETSUM
Notes 12 - Apr. 22
NP-Completeness: Reduction from SUBSETSUM to PARTITION, PARTITION to MAX-CUT
SUBSETSUM: {A={a_1, ..., a_j}, b}, find a subset I of A: (\sum_{i \in I} a_i)=b
Reduce SUBSETSUM to PARTITION: {c_1, ... , c_r}, where r=j+2, c_{r-1}=b+1, c_r=\sum(a_i)-(b-1)
MAX-CUT: Given G(V,E), W, and assignments of weights over the edges, find a subset N of V, that the sum of edges on the cut is bigger or equal to W
Prove MAX-CUT is NP-Complete:
Karp: PARTITION->MAX-CUT: w_{i,j}=c_i*c_j, W=(\sum_i (c_i)^2)/4
Sipser's book: 3SAT->MAX-CUT (in exercises)
Hardness of approximation: weighted MAX-CUT: with factor 2, could be approximated with an randomized algorithm in polynomial time.
Notes 13 - Apr. 29 (Last class)
Intro to RP, BPP
Another way of interpreting complexity class P - if L is in P:
if x is in L, then M(x) output "accept" with probability 1;
if x is not in L, then M(x) output "accept" with probability 0.
Adding randomness: example of an algorithm A' checking if an calculation of adding two numbers is correct or not: A' only check the last bit of the output - When A' detect the last bit is correct, A' accept; if not then reject.
Therefore, if x is in L, then A'(x) output accept with probability 1,
if x is not in L, then A'(x) output accept with probability 1/2
Clarification of HW10 - Problem 3, besides the solution, there're several points to clarify:
- About "error probability": when we say the definition of a machine M with randomness, which has completeness (i.e., when x is in the language) c (accept with probability c) and soundness (when x is not in the language) s (accept with probability s), the error probability is only meaningful when c+s=1, for example, when c=3/4 and s=1/4, the error probability is 1-3/4=1/4. It's not "c-s" - for example, if we have a machine M' which is exactly a coin tosser - whatever the instance is, it accept with probability 1/2, which means c=s=1/2. The error probability for it is equal to 1-1/2=1/2.
Intro to Computation models, Turing Machine. For your reference: Circuit and Finite Automata.
Notes 02 - Feb. 4
Understanding Turing Machine and Transition Table, Cellular Automaton. Game of life, FYI
An Turing Machine Simulator
Notes 03 - Feb. 11
Handling Universal Turing Machine. Summary of computation models
Undecidability of the spectral gap
Notes 04 - Feb. 20 (WED, subst. Feb. 18)
A survey over the cost of basic arithmetic and integer factoring, see this [section 3-5] and this.
Notes 05 - Feb. 25
The P vs NP poll, FYI
Definition of P and NP:
Polynomial-time solvable language L: for all x in L, a machine M running in time polynomial to the length of |x|
NP language L: for all x in L, given a witness w (|w|=polysize(|x|)), M(x,w)->1, running in polytime.
Examples of NP problems:
Integer Factoring (in both NP and CoNP),
PATH (Given a graph and two points, find a path from A to B, in P, using BFS or DFS, in Polytime),
CYCLE (Given a graph, decide whether there's a CYCLE in the graph, in P),
Independent set (Given a graph G with N nodes, a number k<=N, decide whether there's a set of nodes with size >=k, that no edges between each pair of nodes),
CLIQUE (Complement of INDSET)
Notes 06 - Mar. 4
Polynomial-time-reduction, examples:
INDSET<->CLIQUE:
Given an instance x (a graph G<n,k>) in INDSET, pick the complement of G: G' (put edges on where there's no edges on the original graph G, so that if there's a CLIQUE in G'<n,k>, there's an INDSET in G<n,k>)
SubsetSum->0-1 Programming
Notes 07 - Mar. 18
Cont. (map of) Karp reductions, proof of NP-completeness.
Reducing CLIQUE <n,k> to CLIQUE<2n,n>: add n nodes in the original G, pick n-k of them and connecting with every other nodes in the graph.
Notes 08 - Mar. 25
Mid-term review, direction of reduction
Notes 09 - Apr. 01 - A good day to talk about undecidability!
Recap: constructive way of proving there are some language/function:"UC" that is uncomputable.
Reduce UC to the undecidability of HALTING problem.
An example: if the HALTING problem is decidable, then we can prove/disprove Goldbach's Conjecture
Hint of problem 1, problem 3 in HW7
Problem 1: Enumerating all the strings wa, wb, ... in the set of alphabet, using the UTM to decide whether Mi could decide wj, if not, ...
Problem 3: Reducing HALTING problem to this problem. You may like to take reference from http://www.cs.bu.edu/~gacs/papers/Lovasz-notes.pdf, Corollary 3.1.3.
Notes 10 - Apr. 08
Review of Undecidability, prove of undecidability: the set of <M>s that M always halts on some given input string 'a' (including empty input tape) is undecidable.
Notes 11 - Apr. 18 (THU, subst. Apr. 15)
Review the reduction from 3SAT to 0-1 PROG, to SUBSETSUM
Notes 12 - Apr. 22
NP-Completeness: Reduction from SUBSETSUM to PARTITION, PARTITION to MAX-CUT
SUBSETSUM: {A={a_1, ..., a_j}, b}, find a subset I of A: (\sum_{i \in I} a_i)=b
Reduce SUBSETSUM to PARTITION: {c_1, ... , c_r}, where r=j+2, c_{r-1}=b+1, c_r=\sum(a_i)-(b-1)
MAX-CUT: Given G(V,E), W, and assignments of weights over the edges, find a subset N of V, that the sum of edges on the cut is bigger or equal to W
Prove MAX-CUT is NP-Complete:
Karp: PARTITION->MAX-CUT: w_{i,j}=c_i*c_j, W=(\sum_i (c_i)^2)/4
Sipser's book: 3SAT->MAX-CUT (in exercises)
Hardness of approximation: weighted MAX-CUT: with factor 2, could be approximated with an randomized algorithm in polynomial time.
Notes 13 - Apr. 29 (Last class)
Intro to RP, BPP
Another way of interpreting complexity class P - if L is in P:
if x is in L, then M(x) output "accept" with probability 1;
if x is not in L, then M(x) output "accept" with probability 0.
Adding randomness: example of an algorithm A' checking if an calculation of adding two numbers is correct or not: A' only check the last bit of the output - When A' detect the last bit is correct, A' accept; if not then reject.
Therefore, if x is in L, then A'(x) output accept with probability 1,
if x is not in L, then A'(x) output accept with probability 1/2
Clarification of HW10 - Problem 3, besides the solution, there're several points to clarify:
- About "error probability": when we say the definition of a machine M with randomness, which has completeness (i.e., when x is in the language) c (accept with probability c) and soundness (when x is not in the language) s (accept with probability s), the error probability is only meaningful when c+s=1, for example, when c=3/4 and s=1/4, the error probability is 1-3/4=1/4. It's not "c-s" - for example, if we have a machine M' which is exactly a coin tosser - whatever the instance is, it accept with probability 1/2, which means c=s=1/2. The error probability for it is equal to 1-1/2=1/2.