_P means polynomial-time reduction. Please do not copy the answers from: http://

Question

_P means polynomial-time reduction. Please do not copy the answers from:

http://www.chegg.com/homework-help/questions-and-answers/1-answer-t-f-question-well-give-short-justification-answer-one-two-sentences--8-problems-b-q27524367?trackid=3c03fbc0&strackid=13f93cdb&ii=3

OR

http://www.chegg.com/homework-help/questions-and-answers/1-answer-t-f-question-well-give-short-justification-answer-one-two-sentences--8-problems-b-q27524367?trackid=3c03fbc0&strackid=13f93cdb&ii=3

I don't think they're all TRUE like the answers above since the Sorting Problem doesn't reduce to all problems.

1. Answer T/F for each question below, as well as give a short justification for your answer (one or two sentences). 8 (a) For all problems B, Sort

Explanation / Answer

Solution:

a)

False,

This cannot be true, all problems cannot be reduced to sorting problem.

b)

True,

Since A is already non-polynomial it can be reduced to non-polynomial also, so the given statement is wrong.

c)

True

Explanation:

If there was a know polynomial time algorithm for B and not for A then, in this case, A wouldn't has been polynomially reducible to B. because then A is not a subroutine of B otherwise it would have been polynomially solvable.

d)

True

This is the meaning of polynomial time reduction.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.