0
$\begingroup$

Given a known strongly NP Complete problem $A$. If there is a polynomial time transformation from $A$ to another problem NP Complete problem $B$ does that imply anything about if $B$ is always/automatically strongly NP complete or not?

I don't think that it is necessary that $B$ is always/automatically strongly NP Complete but some other sources seem to suggest the opposite. Thus a bit confused.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Take any strongly NP Complete problem for A and any NP Complete B for which we know a pseudo-polynomial time algorithm. Is there a poly-time reduction from A to B? (remember that B is NPC). That should answer your question. $\endgroup$
    – Tassle
    Commented Oct 11, 2022 at 10:38
  • $\begingroup$ @Tassle why don't you post your comment as an answer so we can upvote it and it can be accepted? $\endgroup$
    – Nathaniel
    Commented Oct 11, 2022 at 10:39
  • $\begingroup$ @Nathaniel Yep I should have. Done $\endgroup$
    – Tassle
    Commented Oct 11, 2022 at 10:41

1 Answer 1

Reset to default
2
$\begingroup$

Take any strongly NP Complete problem for A and any NP Complete B for which we know a pseudo-polynomial time algorithm. Is there a poly-time reduction from A to B? (remember that B is NPC) That should answer your question.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks. so I take a strongly NPC simply cannot be transformed to a weak NPC in Polynomial time? (just reconfirming) didn't see transformation of strongly NPC and this part mentioned anywhere..! thanks again. $\endgroup$
    – TheoryQuest1
    Commented Oct 11, 2022 at 10:45
  • 1
    $\begingroup$ @TheoryQuest1 You got it kinda backwards. A weakly NPC problem is still an NPC problem, so any problem in NP (including strongly NPC problems) can be poly-time reduced to it. This is a counter example to the claim that such a reduction proves strong NP completeness. (You actually need the reduction to produce at most polynomially large numerical parameters if you want to prove strong NP completeness) $\endgroup$
    – Tassle
    Commented Oct 11, 2022 at 11:07
  • $\begingroup$ aah.. I initially was sure of the same thing thus the "don't think that it is necessary that B is always/automatically strongly NP Complete.." but your comment threw me off :) $\endgroup$
    – TheoryQuest1
    Commented Oct 11, 2022 at 11:28

Your Answer

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

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