0
$\begingroup$

I have two problems, one of which is solved using dynamic programming. I showed that it is NP-complete (a knapsack variant), therefore having this dynamic programming solution says that this one is weakly NP-complete. Right?

Then, in the second problem I have added a new dimension to the problem which makes is more complicated. It is still NP-complete and I assume that this one is strongly NP-complete.

Is there a way to prove that it is 'strongly' NP-complete?

Update:

I can show that the second problem needs to solve $2^n$ instances of the first problem, where $n$ is the size of problem.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You've asked two questions. To answer the first question:

Not quite right. It depends on the running time of your dynamic programming algorithm. To show that the problem is weakly NP-complete, you should show that there is an algorithm whose running time is polynomial if the input is represented in unary. So, you'll first need to prove that your dynamic programming algorithm has that property.

To answer the second question:

If in doubt, go back to the definition. Wikipedia has a page with a definition of strongly NP-complete; it says

A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

So, that's what you need to prove. It's hard to say much more without knowing what the specific problem is.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.