Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • 1
    $\begingroup$ This actually doesn't prove that the problem is NP-complete, since it's an oracle reduction rather than a many-one reduction. Maybe your professor or TA should brush up on the basics. $\endgroup$ Commented Nov 12, 2016 at 15:08
  • $\begingroup$ @YuvalFilmus What are oracle reduction and many-one reduction? I only heard about reduction as : Let be $(P_1)$ and $(P_2)$, two reconnaissance problem, we say that $(P_1)$ is reducted (or reducible) to $(P_2)$ if * It exists an algorithm for $(P_1)$ that calls to an algorithm of $(P_2)$. * $(P_1)$ is polynomial. I don't fully understand this definition, especially the last condition. $\endgroup$ Commented Nov 12, 2016 at 15:14
  • 2
    $\begingroup$ This defined an oracle reduction. NP-completeness is defined with a different notion of reduction, many-one reduction. There are many online resources about both types of reductions. Sometimes oracle reductions are called Cook reductions or Turing reductions, and many-one reductions are sometimes called Karp reductions. This should give you enough keywords to search for. $\endgroup$ Commented Nov 12, 2016 at 15:26
  • $\begingroup$ You may want to check out our reference questions. $\endgroup$ Commented Nov 12, 2016 at 18:41
  • $\begingroup$ In case someone else was wondering why this doesn't prove NP-completeness: cstheory.stackexchange.com/q/138/50429 $\endgroup$ Commented Feb 6, 2023 at 10:29