1

According to multiple definitions and my math professor, problems in $NP$ can be rewritten to a problem in $NPC$, including problems in $P$. Why can I solve a $P$ problem in polynomial time, but can't solve the $NPC$ version in polynomial time. Are the two problems not the same? Did I create a different problem by rewriting it?

The problem in my train of thought is probably that I don't understand how rewriting a problem works. Right now, I thought it was like 2 + 2 = 3 + 1, but it looks like it is something like 2 + 2 = e/pi, making the problem much harder.

P to NPC

Emiel Steerneman
  • 43
  • 1
    I think your professor means that you can reduce solving an NP problem to an NPC problem. This means if you give me an instance $A$ of an NP problem, I have a polynomial time transformation of that problem to a problem $B$, which is an instance of the NPC problem, so that, you get the same answer from solving $B$ that you would get for solving $A$. If your first problem happens to be in $P$, then the reduction is really boring: It says "just solve the problem, and output the answer", you can do this is polynomial time because we started in $P$. – James Apr 07 '15 at 15:05
  • Thanks for your answer, but I still don't get it. If I can transform P to NPC, why can't I transform NPC to P by doing the opposite? It's like saying 2 + 2 = 3 + 1, but 3 + 1 != 2 + 2. – Emiel Steerneman Apr 07 '15 at 18:10
  • No, it isn't like saying that. You are transforming one object to another (i.e. you are applying a function), if you want to reverse that process, you need that function to be a bijection, which I doubt it will be. – James Apr 07 '15 at 18:20

0 Answers0