COMP3027 Assignment 5
COMP3027代写 4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?
Task 1: [30 marks] COMP3027代写
Consider the following decision problem:
- 4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?
(i)Prove that 4-SAT ∈NP
(ii)Prove that 4-SAT ∈ NPHard
(iii)Thereby prove that 4-SAT ∈ NPComplete
Task 2: [30 marks] COMP3027代写
Consider the following decision problems:
- Minimum-Spanning-Tree: Given a weighted graph tt = (V, E) and an integer d, does there exist a spanning tree of tt with weight at most d?
- Minimum-Spanning-2-Forest: Given a weighted graph tt = (V, E) and an integer d, does there exist a pair of subtrees T1= (V1, E1) and T2 = (V2, E2) of tt, such that V2 = V \ V1 (i.e. each vertex of tt is in either T1 or T2), and the weight of the two trees sum to at most d? COMP3027代写
(i)Provethat Minimum-Spanning-2-Forest P Minimum-Spanning-Tree (you may assume that the weights are positive and that the graph has at least 2 vertices)
(ii)Use this reduction to help you prove that Minimum-Spanning-2-Forest ∈P
Task 3: [40 marks] COMP3027代写
Consider the following decision problem:
- Alternating-Hamiltonian-Cycle: Given a graph tt = (V, E), and a subset A V of its vertices, does there exist a Hamiltonian Cycle of tt, such that the cycle alternates between vertices in A and vertices in V \ A?
For example, if V = {a1, a2, a3, b1, b2, b3} and A = {a1, a2, a3}, and there were edges between every vertex, then the answer would be YES, because a1, b1, a2, b2, a3, b3, a1 is both a Hamiltonian cycle and alternates between vertices in A and vertices not in A. COMP3027代写
(i)Prove that Alternating-Hamiltonian-Cycle ∈NP
(ii)Prove that Alternating-Hamiltonian-Cycle ∈ NPHard
(iii)Thereby prove that Alternating-Hamiltonian-Cycle ∈ NPComplete
Submission details COMP3027代写
- Submission deadline is Sunday 10th June, at 23:59pm. Late submissions without special consider- ation will be subject to the penalties specified in the first lecture (25% per day or part thereof.)
- Submit your answers as a single document (preferably a pdf or doc file) to Canvas. Your work must be typed text (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise. COMP3027代写
- Your assignment will be subject to automatic and manual plagiarism detection systems. Remember, it’s acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as (but not limited to) parts of the actual algorithms, (counter)examples, proofs, writing, or code.
Level of detail required in this assignment COMP3027代写
Please do not write pseudocode (it’s an unnecessarily precise level of detail for these reductions, and usually harder to follow than prose.)
- Please try to be fairly concise.
- It’sreasonable to write things like these without having to explain precisely how it’s done:
-‘checkthat P is a simple path’ COMP3027代写
-‘checkthat all the subsets are disjoint’
- You don’t need to detail data structures etc., unless the choice of structure is important for showing that the time complexity is still polynomial.
- Don’t forget that you’re not trying to solve these problems, you only need to find polynomial time certifiers / polynomial time reductions as appropriate.
Appendix: NP Complete problems
This is just a short list of some well known NP Complete problems that have been mentioned in lectures, in case you need inspiration for problems to reduce from for your NP Completeness proofs. COMP3027代写
- 3-Colour: Given a graph, is it possible to colour the vertices using at most 3 colours, such that no pair of adjacent vertices have the same colour?
- 3-SAT: Given a formula in Conjunctive Normal Form, where each clause has exactly 3 literals, is there a satisfying truth assignment?
- Circuit-SAT: Given a combinatorial circuit of AND, OR, and NOT gates, is there a way to set the circuit inputs such that the output is 1?
Hamiltonian-Cycle: Given a graph, is there a simple cycle which visits every vertex of thegraph?
- Independent-Set: Given a graph tt = (V, E) and an integer k, is there a subset of vertices S ⊆V such that |S| ≥ k and for each edge at most one of its endpoints is in S?
- Knapsack: Given a set of items with weights and values, an integer capacity C, and an integer k, is it possible to select a subset of items with total weight no greater than C, but total value at least k?
- Set-Cover: Given a set of elements U , a collection of subsets of it, and an integer k, does there exist a collection of k of these subsets whose union covers U ? COMP3027代写
- Subset-Sum: Given a set of integers S and an integer k, is there a subset of S which sums to k?
- Traveling-Salesman-Problem: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length ≤D? COMP3027代写
- Vertex-Cover: Given a graph tt = (V, E) and integer k, is there a subset of vertices S ⊆ V such that |S| ≤ k and for each edge at least one of its endpoints is inS?
其他代写：代写CS C++代写 java代写 matlab代写 web代写 app代写 作业代写 物理代写 考试助攻 paper代写 金融经济统计代写
