logo Hurry, Grab up to 30% discount on the entire course
Order Now logo

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Persimmon BissoondathBusiness
(4/5)

753 Answers

Hire Me
expert
Adrian ReedFinance
(5/5)

616 Answers

Hire Me
expert
Barry CresswellStatistics
(5/5)

950 Answers

Hire Me
expert
Vivek ChauhanComputer science
(5/5)

879 Answers

Hire Me
Computer Science

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

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme