Exercise 3 (2 pts). Consider the following decision problem: Given a graph G and
ID: 3741144 • Letter: E
Question
Exercise 3 (2 pts). Consider the following decision problem: Given a graph G and an edge e in it, determine whether G has a cycle containing e. Is this problem in P? Yes, no, unknown? Justify your answer (if your answer is "yes", briefly describe a polynomial-time algorithm) Exercise 4 (1 pt for each correct answer). 1. True, false, or unknown: Every problem in NP can be solved in polynomial time. 2. True, false, or unknown: Every problem in NP cannot be solved in polynomial time. 3. True, false, or unknown: Every problem in EXP can be solved in polynomial time. 4. True, false, or unknown: Some problems in EXP can be solved in polynomial time.Explanation / Answer
SOLUTION:(4)-
(1):-FALSE
(2):-TRUE
(3):- FALSE
(4):-FALSE
SOLUTION(3):- Given a Graph G and an Edge e in it. Determining the Hamiltonian Cycle in this Graph can not be called Decision Problem. Actually There is no polynomial time algorithm investigated yet for finding a Hamiltonian cycle in a Graph, it is called NP-Complete with undecided status. This is not in P because it can not be solved in polynomial time algorithm. You can only verify NP-Complete problems in polynomial time but you can not find the appropriate solution of these in polynomail time. Although this type of problem will be solved in Exponential Time with implementation of exhaustive search method.
=======================================================================================
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.