CSCC63 Assignment 3
Polytime Reductions, Self-Reductions, and PS Due 11:59pm, August 7
Warning: For this assignment you may work either alone or in pairs. Your electronic submission of a PDF to Crowdmark affirms that this assignment is your own work and that of your partner, and no one else’s, and is also in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCC63. Note that using Google or any other online resource is considered plagiarism.
1. (10 marks) Consider the language MIN-BLOCKS defined as: Instance: A matrix M and an integer k.
Question: We’re allowed to permute the rows and columns of M as we like, and we want to do so in a way that minimizes the number of single-number rectangular “blocks” needed to describe thematrix. E.g.,isweweretowrite(a,b,c,d;137),where16a6c6mand16b6d6n, thenwewouldknowthateveryentryMi,j fora6i6candb6j6dwouldhavethenumber 137.
Our question is, can we permute the rows and columns of M in such a way that we need no more than k blocks to store it?
As an example, if M is
101 222,
then we can permute the second and third row and the first and second columns to get
011 211.
We need four blocks to describe the matri we get from this permutation:
011 211,
011 211,
011 211,
011 211.
Notice that we allow the third and fourth blocks to overlap, since they store the same number.
You will also find that we can’t use fewer than four blocks to store this matrix, regardless of the permutation. SoifIgiveyouM andkfork>4,itwillbeyes-instance. IfIgiveyouak<4it will be a no-instance.
Programming Help, Add QQ: 749389476
You can assume this language is in NP, but you have to show that it is NP-complete (so you have to show that it’s NP-hard).
With this in mind, give a reduction that shows MIN-BLOCKS is NP-hard. Reduce from some language in the Polytime Reduction Examples 1 or the Polytime Reduction Examples 2 handout.
2. (10 marks) Consider the language CLOSE-SOLUTION-3SAT defined as: Instance: A 3CNF φ and a satisfying truth assignment τ for φ.
Question: Does φ have a second satisfying truth assignment τ′ ̸= τ such that τ and τ′ agree on at least 7/8 of their variable assignments?
You can assume this language is in NP, but you have to show that it is NP-complete (so you have to show that it’s NP-hard). With this in mind, give a proof that CLOSE-SOLUTION-3SAT is N P -hard.
3. Consider the language PATH-CONSTRAINT defined as:
Instance: A directed graph G = (V, E), two vertices s and t, and two numbers r and k.
Question: Can we find a size-r subset R of vertices in V such that if PR is the longest simple path from s to t using only vertices in R, then the number of vertices in PR is somewhere between 2 and k−1?
(a) (10 marks) Show that PATH-CONSTRAINT is NP-hard (and therefore not likely to be in co-N P ).
(b) (10 marks) Show that PATH-CONSTRAINT is co-NP-hard (and therefore not likely to be in NP). Reduce from some language in the Polytime Reduction Examples 1 handout.
(c) (10 marks) Show that PATH-CONSTRAINT ∈ PS.
4. (10 marks) Let f be the polytime reduction from TQBF to GG (generalized geography) as described
Let φ = ∀x1, x2∃x3, ∀x4(¬(¬x1 ∨ ¬x2) ∨ x2 ∨ ¬(¬x1 ∧ (x3 ∨ x4))) ∧ x3 ∧ (¬x1 ∨ x4).
Draw f(φ) (do not simplify the formula before applying f). Label your graph appropriately and indicate the starting node.
5. (10 marks) Recall the STORAGE-BOX language, as given in assignment 2.
You’ve already given a proof that this language is NP-complete, but we can also ask how, given an
oracle for STORAGE-BOX, to find a solution for a particular STORAGE-BOX instance.
Show how you can use an oracle for STORAGE-BOX to build a polytime oracle program FIND-
STORAGE-BOXES such that for any instance of STORAGE-BOX:
If any solution exists for that instance, FIND-STORAGE-BOXES will return some such so-
If no such solution exists, FIND-STORAGE-BOXES will return null.
Justify why your program is correct and runs in polytime.
6. (10 marks) Recall the FEEDBACK-ARC-SET language, as given in the Polytime Reduction Examples 1 on the course website.
You’ve already been given a proof that this language is NP-complete, but we can also ask how, given an oracle for FEEDBACK-ARC-SET, to find an optimal feedback arc set for a particular directed graph G.
Code Help, Add WeChat: cstutorcs
Show how you can use an oracle for FEEDBACK-ARC-SET to build a polytime oracle program MINIMIZE-FEEDBACK-ARC such that takes as input any directed graph G and returns a small- est feedback arc set for G.
Justify why your program is correct and runs in polytime.
7. (10 marks) Consider the 3DM language, as given in the Polytime Reduction Examples 1 handout on the course website.
Modify the NP-hardness proof for 3DM to make it a parsimonious reduction from #3SAT.
8. (10 marks) Consider again the FEEDBACK-ARC-SET language, as given in the Polytime Reduction Examples 1
handout on the course website.
Modify the NP-hardness proof for FEEDBACK-ARC-SET to make it a parsimonious reduction.
9. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5)
Consider the SPIRAL-GALAXIES reduction described in the Polytime Reduction Examples 2 hand- out.
Note: This handout won’t be out at the time Assignment 3 is posted, but it will be up soon.
In this reduction we encode a number of widgets that represent wires, inputs, and-gates, and other circuit components, and we use those components to build a representation of a 3CNF φ. But in that reduction we miss one component: we don’t show a way to bend the wired we build, and so we re forced to use a workaround in which the circuit wires always face in the same direction and move laterally by shifting.
Technically we’d also need to modify the crossover widget to get this to work as well, but this is the interesting part.
To answer this question, find a way to encode a bent wire (using the endcoding from the reduction) into a SPIRAL-GALAXIES game. Carefully explain why your widget works.
程序代写 CS代考 加微信: cstutorcs