Discussion
Which of the following is not true for problem reducibility ?
Answer: A
The statement that is not true is Satisfiability is not reducible to halting problem.
Satisfiability is decidable, and every decidable problem reduces to the halting problem: map each yes-instance to a machine that halts and each no-instance to one that loops, which a decider for SAT can do. So SAT is reducible to the halting problem.
The other statements are true. SAT is in NP and every other NP-complete problem is NP-hard, so SAT reduces to each of them. An optimisation problem can be solved with polynomially many calls to its decision version, for example by binary search on the bound. And reducibility is transitive: if A reduces to B and B to C, then A reduces to C.
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