Np-hardness reduction

Question

If I want to show that a problem is np-hard is it ok to use a existing np-hard problem multiple times? For example use Hamiltonian Cycle n times in a graph where n is the number of vertices? Or do I need to transform the graph into something that can easily be solved by an existing np-hard problem used 1 time?

Answer 1

You need to show the exact oposite.

It doesn't prove anything if you prove you can solve your problem with an NP-Hard problem. [You can solve every problem in NP using SAT, by Cook-Levin Theorem].

You need to show that if your problem is solvable in polynomial time - so is an NP-Hard problem. That what a reduction actually does.

For example: If I can show I can solve shortest path, using TSP - does it make shortest path NP-Hard? Of course not! It only shows TSP is at least as hard as shortest path!

Answer 2

I'm not a mathematician, but surely if you can prove that the problem in question is at least as complex as an existing known-to-be-NP-hard problem, or multiples thereof, than that should be sufficient proof? Common sense would suggest that if skinning a leopard is more complex than skinning 2 cats, then its more complex than skinning one cat, and so on!

Answer 3

traveling from paris to london via new york doesn't prove that that path is the shortest one.