1
$\begingroup$

I have a decision problem $X$ of which I think I can show its complexity by using a reduction from a problem $Y$ that has been shown to be strongly NP-hard.

I tried to follow the same procedure as for proving NP-completeness which I try to summarize here:

  1. Show that problem $X$ is in NP (polynomial time verifiable)
  2. Make the Karp reduction from a known NP-complete problem by finding a poly-time algorithm that transforms the instances $y$ of $Y$ to instances $x$ of $X$
  3. Show correctness of algorithm: Show that for every yes/no answer to an instance of $Y$, the algorithm also returns yes/no

The problem I'm currently facing concern point 1 and 2:

  • I'm sure that $X$ is in NP, but $Y$ is not necessarily, right? Is it a problem when I try to reduce an NP-hard problem to an NP-complete one?
  • The strongly NP-hard problem $Y$ is not necessarily NP-complete, right? Can I still use $Y$ here?

Another open question regards the fact that $Y$ is strongly NP-hard:

  • Assuming that I can do the reduction as outlined above, is then $X$ also strongly NP-complete?
$\endgroup$
  • 1
    $\begingroup$ Can you add the definition of strongly NP-hard and strongly NP-complete? $\endgroup$ – Yuval Filmus Aug 26 '16 at 13:11
  • $\begingroup$ @YuvalFilmus Unfortunately, the authors of the work in which $Y$ is shown to be strongly NP-hard do not give their definition of this. I therefore assumed that they use the definition also given in en.wikipedia.org/wiki/Strong_NP-completeness. $\endgroup$ – bonanza Aug 26 '16 at 13:22
  • 2
    $\begingroup$ You cannot show that a problem is NP-hard using the reductions you mention in (2). NP-hardness is defined using many-one reductions rather than using oracle reductions. $\endgroup$ – Yuval Filmus Aug 26 '16 at 13:26
  • $\begingroup$ @YuvalFilmus, thanks for your reponse. I'm sorry I forgot about the difference between Karp and Cook reductions. I actually meant Karp reductions. I will change the question. $\endgroup$ – bonanza Aug 26 '16 at 13:28
  • 1
    $\begingroup$ A Karp reduction to "a known NP-complete problem" does not show NP-hardness. ​ (You need a reduction from an NP-hard problem.) ​ ​ ​ ​ $\endgroup$ – user12859 Aug 26 '16 at 16:48
2
$\begingroup$

I will assume that your definition is the one on Wikipedia.

We wish to prove that $X$ is strongly NP-Complete. Here's how you do that. First, show that $X$ is strongly NP$^1$. Next, find a strongly NP-Complete problem $Y$ and reduce $Y$ to $X$. That is, provide an algorithm which takes an instance $y$ of $Y$ and produces $f(y)$ such that if $y\in Y$ then $f(y)\in X$ and otherwise, if $y\not\in Y$ then $f(y)\not\in X$.

I remember in which way to reduce a problem (was it $X$ to $Y$ or $Y$ to $X$?) by framing it as a conversation which I've laid out here in this other answer(link): someone challenges me by saying $X$ is easy. Then I say, nonsense, if $X$ were easy, then I could solve very hard problem $Y$. And then I show how to do that: I take an instance of $Y$, rewrite it into an instance of $X$, and then you're done. You've shown that $X$ is at least as hard as $Y$, so we write $Y\leq X$.

$^1$ best I can figure, strongly NP means it has logarithmically-sized certificates

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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