CODEWITHSUNDEEP
algorithmnp-completenp-hardnp
Mads Andersen
Mads Andersen

Reputation: 3153

Np-hardness reduction

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?

Upvotes: 0

Views: 492

Answers (3)

xyz
xyz

Reputation: 201

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

Upvotes: 1

amit
amit

Reputation: 178441

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!

Upvotes: 4

Simon Withington
Simon Withington

Reputation: 1485

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!

Upvotes: 0

Related Questions