0

The logic used goes like this - we have an existing class of problems that are NP-Complete. Now a new problem "Q" comes up.

Step 1 - We prove Q is in NP, well and good.

Step 2 - We show that a problem in NP-C(say O) is reducible to Q. (O - > Q)

Now we say that because O is NP-Hard, and because it is reducible to Q, Q must also be NP-hard since there is no simpler solution for O, and were Q a simpler solution, then we could just reduce O -> Q and solve Q.

However, we don't know for sure yet that P!=NP. Maybe this new problem Q was the problem that could actually be solved in polynomial time, and that to solve each of the problems in NPC we only need to convert them to Q and then Q needs to be solved. If so, how is step 2 a valid proof for Q being NP-Hard?

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
Suyash Kumar
  • 11
  • 3

2 Answers2

0

NP-hard is a definition involving certain complexity classes, namely NP and NP-complete. The definitions do not refer to the complexity class P. Poly-time reduction in itself does not refer to P. Think of using a vocabulary from which the notion P has been stripped.

The definitions and theorems thus remain valid when notion P is introduced to the vocabulary. It may be the case that the notion P is actually mathematically equivalent to the notion NP. That still does not invalidate definitions and theorems phrased in terms of N-notions, it would just open up a richer theory to discuss them.

collapsar
  • 17,010
  • 4
  • 35
  • 61
0

I believe that your problem here hinges on some misunderstandings of the definitions of NP, NP-Complete, and NP-Hard.

This is a good prior answer explaining those definitions: What are the differences between NP, NP-Complete and NP-Hard?

Note, unlike in the answer stated above, NP-Hard consists of problems in NP as well as problems not in NP that are AT LEAST as hard as NP problems.

To specifically answer your question, step 2 is a valid method of showing a problem is NP - hard because if an existing problem can be transformed into Q, then Q is AT LEAST as hard as O. If, like you said, you found a P time solution to Q, that does not mean that Q is no longer in NP-Hard. It simply means that you have found a way to solve all NP hard problems that exist in NP, or more simply P=NP. This does not remove the definition of NP-Hard however. An analogy might help your understanding. Suppose you discovered a new species, and over time you realize it belongs to a family of animals already discovered. This would make the species a part of the wider family, but it would still retain its own traits that make it unique.

Charlie MacVicar
  • 1