CS 312 (W'07, T Th sections)

12.49 seems to require a lot of in-depth understanding of transforming NP-complete problems into each other. In class, I thought we clarified that an in-depth understanding of these transformations were deep and outside the scope of this class. Maybe I came away with the wrong idea. In any case, a proof of this question is deeper than I (or TA Ryan) could give. Can anyone help me with what is expected for this problem? Thanks.

Andrew (or anyone else),

I didn't bring my book home could you tell me what the question is for 12.49? Once I get that, I'll post some hopefully useful info.

Mike.

12.49:

Prove that any two NP-complete problems arae polynomially Turing equivalent.

Ok, that's a question that looks like you need to know deep complexity theory about NP completeness but you really don't. I sketch out why. My goal here is to set up the probme in a way that makes it easier to see the solution without giving away the solution. That way you get the joy of the "aha" moment :)

"polynomially Turing equivalent" means that problems A and B are polynomially Turing equivalent if A is polynomial-Turing-reducible to B and B is polynomial-Turing reducible to A. Polynomial-Turing-reducible is that less-than-or-equal-to sign with a T subscript and a p superscript. A is is polynomial-turing-reducible B if the following fact is true:

There is an algorithm for solving A. That algorithm runs in polynomial time (on a deterministic Turing machine). That algorithm is allowed to ask a question of the form "is a solution for B" as often as it likes and it gets an answer to that question in 1 time unit

So that's polynomial Turing equivalence.

Your objective is to show that any two NP-complete problems are polynomial Turing equivalent. So you need to show that they are both reducible to each other.

You get to assume that both problems are NP-complete. The key to this problem is to exploit that assumption. A problem X is NP-complete if it is

1. X is in NP
   
2. All other problems in NP are polynomial-Turing-reducible the X.
   

Hopefully that's enough to see the solution without doing all the work for you. Have fun with it!

Mike.

Aha! Thanks for the explanation.

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)

URL:
Remember me? YesNo

Comments: