Discussion
Which of the following is not true for the problem classes P, NP, NP-complete and NP-hard ?
Answer: C
The statement that is not true is NP-hard ⊂ NP.
A problem is NP-hard if every problem in NP reduces to it in polynomial time. It need not be in NP itself: the halting problem is NP-hard but undecidable, so it is not in NP, and optimisation versions of NP-complete problems are NP-hard without being decision problems in NP.
The other relations hold. P is contained in NP, since a problem solvable in polynomial time can be verified in polynomial time. NP-complete problems are by definition both in NP and NP-hard, so NP-complete is contained in NP and in NP-hard.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development