0

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?

Improve this question
1
  • 1
    @PeteKirkham: cstheory is for research level questions. This question will be closed, as it is off-topic for cstheory. Commented Jan 9, 2012 at 13:44

3 Answers 3

Reset to default
4

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!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I think this answered my question. I have to transform my problem(in polynomial time) so that it can solved by a known NP-Hard problem. This also means that I should only be using the known NP-Hard problem 1 time to answer my original question.
@MadsAndersen: no. You need to transform the NP-Hard problem to your problem to show it is NP-Hard. or in other words: Use an algorithm for your problem to solve NP-Hard problem. If it can be done in polynomial time - your problem is NP-Hard.
1

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

Improve this answer

Comments

0

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!

Improve this answer

6 Comments

This is nonesense. If I can solve shortest distance between 2 vertices using TSP, does it mean shortest path is NP-Hard?
I'll leave that leopard well alone then - as I said I'm not a mathematician. I did say that if you could prove it was 'at least as complex' not 'solvable with', are you sure you aren't misinterpreting me a little amit?
For the very least it doesn't answers the question. The question has a critical logic failure. every answer that doesn't mention it is basically wrong.
This common sense is called transitivity... Which might be true for a relation and false for the other one.
So even though my suggestion is not incorrect, it is incorrect due to a flaw in the question? I think our understandings of logic are quite different ;)
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.