Quiz Space

Advanced Algorithms · End Term · 3 Sept 2023 · May 2023 term · Set QPE1-S2

Question 2: Let S be an NP-complete problem and Q and R be two other …

Question 2

+3 marksOne correct option

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

  1. A

    R is NP-complete

  2. B

    R is NP-hard

  3. C

    Q is NP-complete

  4. D

    Q is NP-hard

Show answer

Correct answer

  • B

    R is NP-hard

See the whole paperTake it as a mock test

Question 2 of 34 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 3 Sept 2023, in the May 2023 term (IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep). It carries 3 marks.

More questions from this paper

  1. Q1Recall the Dance Class problem: Problem Definition Dance Classes Input: A collection of n intervals given by their left…
  2. Q3True or false?\ It is possible that Independent-Set is in P and the problem of checking a graph has a Hamiltonian Path …
  3. Q4Figure question
  4. Q5Raj and Lata both designed an algorithm for the same minimization problem. Raj proved that his algorithm Alg1 is a 2-ap…
  5. Q6Recall the max-flow problem: for a directed graph G(V, E) with non-negative capacities c_e for every e \in E and two sp…
  6. Q7Figure question
  7. Q8Recall the Dance Class problem: Problem Definition Dance Classes Input: A collection of n intervals given by their left…
  8. Q9Recall the Stable Matching problem: Stable Matching Input: Two sets given by M = {m_1, \ldots, m_n} (the men) and W = {…
  9. Q10Is the collection of outgoing 1/2-factors over the set A a matroid?
  10. Q11Is the collection of incoming 1/2-factors over the set A a matroid?
  11. Q12Is the collection of 1-factors over the set A a matroid?
  12. Q13Can the collection of 1-factors be defined as the intersection of two matroids?
  13. Q14Based on the above data, answer the given subquestions.
  14. Q15The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  15. Q16The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  16. Q17The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  17. Q18The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  18. Q19The memory of Bob's computer contains two interesting things: an array of integers and a virus. Each midnight the virus…
  19. Q20Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity acro…
  20. Q21You are supposed to start at the top of a number triangle and chose your passage all the way down by selecting between …
  21. Q22Consider the following orientation problem. We are given an undirected graph G = (V, E) and integer values p(v) for eve…
  22. Q23Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity acro…
  23. Q24Consider the partially carefully properly 5-colored graph below. What color should we give the vertex in the center to …
  24. Q25Based on the above data, answer the given subquestions.
  25. Q26In the Uncapacitated Facility Location (UCFL) problem, we are given (\mathcal{F} \uplus \mathcal{D}, d) as well auxilia…
  26. Q27Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  27. Q28Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  28. Q29Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  29. Q30Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asteri…
  30. Q31Based on the above data, answer the given subquestions.
  31. Q32Based on the above data, answer the given subquestions.
  32. Q33Based on the above data, answer the given subquestions.
  33. Q34Recall the Traveling Salesman Problem: Definition Traveling Salesman Problem Input: A set of distinct cities {c_1, c_2,…