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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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