[SOLVED] Cscc63 assignment 3 p0

Polytime Reductions, Self-Reductions, and PS
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 the matrix. E.g., is we were to write (a,b,c,d;137), where 1 6 a 6 c 6 m and 1 6 b 6 d 6 n , then we would know that every entry: cstutorcsMi,j for a 6 i 6 c and b 6 j 6 d would have the number 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, ifM is 1 0 1
2 2
1 2 1 then we can permute the
second and third row and the first and second columns to get
.
We need four blocks to describe the matri we get from this permutation:
0 1 1 2 1 1 ,
2 2 2

,

,
2 2 2
and
.
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. So if I give you M and k for k > 4, it will be yes-instance. If I give you a k < 4 it will be a noinstance.
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 程序代写代做 CS 编程辅 MIN-BLOCKS is NP-hard. Reduce
from some 导 language in the Polytime Reduction Examples 1 or the Polytime Reduction Examples 2
handout.
Instance: A 3CNF φ and a satisfying truth assignment τ for φ.

Question: Does φ have a second satisfying truth assignment τ0 6= τ such that τ and τ0 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 NP-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-: cstutorcsr 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?
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.
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 FINDSTORAGEBOXES such that for any instance of STORAGE-BOX:
If any solution exists for that instance, FIND-STORAGE-BOXES will return some such solution.
If no such solution exists, FIND-STORAGE-BOXES will return null. Justify why your program is correct and runs in polytime.
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.
Show how you can use an oracle for FEEDBACK-ARC-SET to build a polytime oracle program MINIMIZEFEEDBACK-ARC such that takes as input any directed graph G and returns a smallest feedback arc set forG. Justify why your program is correct and runs in polytime.
Modify the NP-hardness proof for 3DM to make it a parsimonious reduction from #3SAT.
Modify the NP-hardness proof for FEEDBACK-ARC-SET to make it a parsimonious reduction.
Consider the SPIRAL-GALAXIES reduction described in the Polytime Reduction Examples 2 handout.
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.