(5/5)

Problem (1. Random conversions (SOLO)) In this question, we define 3 new complexity classes

(a complexity class is a set of languages; for example P and NP are complexity classes).

We say that L ∈ PMCO if there exists a randomized algorithm A with the following properties:

• A runs in worst-case polynomial time;

• if x ∈ L, then Pr[A(x) accepts] ≥

1

2

;

• if x 6∈ L, then Pr[A(x) rejects] = 1.

In other words, L ∈ PMCO if there exists a polynomial time Monte-Carlo algorithm A that computes

L with one-sided error. If x 6∈ L, the algorithm does not make an error. If x ∈ L, then the algorithm

errs with probability less than 1

2

. Observe that for x ∈ Σ

∗

, if A(x) accepts, then we know with

certainty that x ∈ L.

We say that L ∈ coPMCO if Σ∗\L ∈ PMCO. Equivalently, L ∈ coPMCO if there exists a randomized

algorithm A0 with the following properties:

• A0

runs in worst-case polynomial time;

• if x ∈ L, then Pr[A0

(x) accepts] = 1;

• if x 6∈ L, then Pr[A0

(x) rejects] ≥

1

2

.

Observe that for x ∈ Σ

∗

, if A0

(x) rejects, then we know with certainty that x 6∈ L.

We say that L ∈ PLV if there exists a polynomial time Las Vegas algorithm that computes L.

Prove that PMCO ∩ coPMCO = PLV. (You should argue both inclusions separately.)

Problem (2. MIN-CUT variant (SOLO)) Consider a variant of the minimum cut problem where

each edge has a cost (positive number), and our goal is to output a cut with minimum total cost

(the cost of a cut is the sum of the costs of the cut edges). The usual minimum cut problem

corresponds to the case where each edge has equal cost.

1

Suppose we modify the randomized algorithm seen in class so that in each iteration, the probability

of picking an edge to contract is proportional to its weight. (We are not giving a full description here,

but we would like you to figure out exactly what this means.) Show that the success probability of

this algorithm is at least 1/n2

. Apply boosting to get an algorithm with error probability at most

1/2

300

.

Hint: Can the analysis done in class be adapted to this setting?

Problem (3. TP approximation (GROUP)) Alan is taking 15-451 this semester. For Homework

17, he is given a problem set with n problems. Unfortunately he has run out of paper, so he decides

to write his solutions on toilet paper. He would like to write the solutions in a way that uses

the least number of toilet paper squares (as toilet paper is a very precious commodity now). The

solution to the i

th problem takes ai units of length to write up where ai

is a real number in the range

(0, 1], for all i ∈ {1, 2, . . . , n}. Each toilet paper square is exactly 1 unit length. Unfortunately,

the TAs are rather eccentric; they demand that each solution must be entirely contained in one

square. A square can contain more than one answer. As an example, suppose n = 3 and a1 = 1/3,

a2 = 5/8, and a3 = 1/2. Then we could write the solutions on two squares: one square contains a2

and the other square contains a1 and a3.

1. Help Alan out by giving a polynomial-time algorithm that uses at most 2 times the minimum

number of toilet paper squares necessary to solve this problem (i.e., give a polynomial-time

2-approximation algorithm).

2. Show that for any > 0, there is no polynomial-time (1.5−)-approximation algorithm for the

above problem unless P = NP. That is, if there is a polynomial-time (1.5 − )-approximation

algorithm, then P = NP.

This is known as a hardness-of-approximation result. We say that the problem is NP-hard to

approximate within a factor better than 1.5.

Hint: You may assume PARTITION is NP-hard.

Problem (4. A random grid (GROUP)) On an m by n grid of squares, color each square black

or white independently with 1/2 probability. Create a graph by creating a vertex for each square,

and putting an edge between two adjacent squares if they are of the same color (adjacent in the

directions up, down, left or right).

1. Consider the special case of m = 1. Show that the expected number of connected components

in the graph is exactly (n + 1)/2.

2. Prove that in the general case, the expected number of connected components in the graph

is at least max{

m+n

2

,

mn

16 }.

Bonus: Show that the expected number is at least mn

8

.

2

Problem (5. If you can decide, you can search (OPEN)) As you know NP is a set of languages (or

decision problems), and if P = NP, then every decision problem in NP (e.g. SAT, TSP, CLIQUE)

can be solved in polynomial time. A priori, perhaps having a fast algorithm deciding SAT, TSP or

CLIQUE may not be very impressive. Typically we are not just interested in whether a Boolean

formula is satisfiable or not, but we want to find a satisfying assignment if there is one. We are not

just interested in whether a graph has a Hamiltonian cycle of cost at most c, but we want to find

such a cycle if it exists. We are not just interested in whether a graph has a k-clique, but we want

to find such a k-clique if it exists.

In this problem, we will show that if P = NP, not only can we solve every decision problem in

NP in polynomial time, but we can also find the solutions to the yes-instances of problems in NP

in polynomial time. For example, if P = NP, given a satisfiable Boolean formula, we can find a

satisfying assignment in polynomial time. And given a graph that has a Hamiltonian cycle of cost

at most c, we can find a Hamiltonian cycle of cost at most c in polynomial time. And given a graph

containing a k-clique, we can find a k-clique in polynomial time.

1. Prove the following assuming P = NP. Given an integer k > 0 and a polynomial time TM V

(with two inputs), there is a polynomial time TM V

∗ with the property that for every x ∈ Σ

∗

,

if there exists u ∈ Σ

∗ with |u| ≤ |x|

k and V (x, u) = 1, then V

∗

(x) outputs a string u

∗

such

that |u

∗

| ≤ |x|

k and V (x, u∗

) = 1.

2. Explain why the above shows that if P = NP, then for every decision problem in NP, there is

a polynomial time algorithm that given a yes-instance of the problem, outputs a polynomiallength “solution” (or “proof”) that certifies that the yes-instance is indeed a yes-instance

(and given a no-instance, outputs “no”). (This part of the problem should be short given the

first part.)

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of