Theoretical Computer Science (U21276)
Part B/9: P, NP and NP-complete-problems (Jan 17-21, 2022)
Please, do some research about the problems below on the Internet!
Question 1. Explain why the following problem is in P:
Copyright By PowCoder代写 加微信 powcoder
Input: a graph G;
Output: YES, if G is an Eulerian graph (has an Eulerian circuit) & NO, otherwise.
Is the problem also in NP? How about the complexity of the problem when the output is YES, if G is non-Eulerian graph.
Question 2. Explain why the following problem is in NP:
Input: a graph G;
Output: YES, if G is a Hamiltonian graph (has a Hamiltonian cycle) & NO, otherwise.
Is the problem also in P? How about the complexity of the problem when the output is YES, if G is non-Hamiltonian graph.
Question 3. Given the following three statements:
(a) P= NP;
(b) P̸= NP;
(c) P̸= NP and all NP-complete problems are intractable.
For each of the following statements, select one of the preceding statements to fill in the blank.
If problem p is in NP and p is provable intractable, then . . .
If problem p is in NP-complete and p is provable intractable, then … If problem p is in NP-complete and p is in P, then …
Question 4.
For each of the following questions, assume that A is an NP-problem.
(a) Suppose you prove a theorem showing that a lower bound for the running time of
any algorithm to solve A is Θ(2n). What would you tell the world?
(b) Suppose you find a deterministic algorithm that solves A in polynomial time. What
would you tell the world?
(c) Suppose A is NP-complete and you find a deterministic algorithm that solves A in polynomial time. What would you tell the world?
(d) Suppose you prove that the 3-satisfiablility problem is polynomially reducible to A. What would you tell the world?
Question 5. The 1-satisfiablity problem is to determine whether a conjunction of literals is satisfiable. Prove that the 1-satisfiability problem is in P by finding a deterministic polynomial algorithm to solve it.
Question 6. Are the following statements TRUE?
“All instances of an NP-complete problem are difficult.”
“Lower bound for solving NP-complete problems requires exponential time.”
“NP-complete problems are the most difficult known problems.”
“NP-complete problems are difficult because there are so many different solutions.”
Question 7. A k-colouring of a graph is an assignment of one colour to each vertex, using a palette of k colours, such that no two vertices joined by an edge receive the same colour.
In the Minimum colouring problem (MinCol) we are given a graph and we are looking for a colouring with the minimum number of colours.
In the decision version of the colouring problem, we are given a graph G and integer k and the question is whether there exists a k-colouring of G.
What do you think is the complexity of MinCol for trees/for bipartite graphs/for complete graphs?
What do you think is the complexity of 2-colouring problem?
Explain why the decision version of the colouring problem is in NP.
What do you think is the complexity of the MinCol problem ?
Question 8. The longest path problem is the problem of finding a simple path of max- imum length in a given graph. A path is called simple if it does not have any repeated vertices.
Knowing that the Hamiltonian path problem is NP-complete (the existence of a path going through all vertices) can you prove that also the decision version of the longest path problem is NP-complete using a polynomial time reduction?
Question 9. The students in one THEOCS tutor group have suggested the greedy algorithm for the minimum vertex cover problem: in each step put a vertex with the maximum degree to the vertex cover, remove it and continue until the graph is empty. Can you prove that their algorithm is correct? What it would imply?
If you think that the algorithm is not correct, can you find a graph for which the algorithm doesn’t return the correct answer?
Question 10. A student in one THEOCS tutor group has suggested that for a colour- ing of any graph it is enough to take as many colours as the number of vertices in a maximum complete subgraph of the given graph. What do you think? Can you find a counterexample or perhaps to prove the statement?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com