## 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.