Quiz Space

Programming, Data Structures and Algorithms using Python · End Term · 1 Sept 2024 · May 2024 term · Set QDF1

Question 14: Let Z be an NP-complete problem and X and Y be two other…

Question 14

+4 marksOne correct option

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

  1. A

    Y is NP-complete

  2. B

    Y is NP-hard

  3. C

    X is NP-complete

  4. D

    X is NP-hard

Show answer

Correct answer

  • B

    Y is NP-hard

See the whole paperTake it as a mock test

Question 14 of 25 in the IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) End Term paper sat on 1 Sept 2024, in the May 2024 term (IIT M FOUNDATION DIPLOMA AN EXAM QDF3 01 Sep 2024). It carries 4 marks.

This question was also asked in

More questions from this paper

  1. Q1Figure question
  2. Q2Figure question
  3. Q3Figure question
  4. Q4Figure question
  5. Q5Figure question
  6. Q6Figure question
  7. Q7Figure question
  8. Q8Figure question
  9. Q9Figure question
  10. Q10Figure question
  11. Q11Figure question
  12. Q12Figure question
  13. Q13Figure question
  14. Q15Figure question
  15. Q16Figure question
  16. Q17Figure question
  17. Q18Figure question
  18. Q19Figure question
  19. Q20Figure question
  20. Q21Consider a binary max-heap implemented using list. Which of the following lists represents a binary max-heap?
  21. Q22Which of the following statement(s) is/are true about Huffman algorithm ?
  22. Q23Figure question
  23. Q24Based on the above data, answer the given subquestions.
  24. Q25What is the time complexity of the given algorithm ?