Re: Reductions in P


Markus Triska wrote:

We know that if one wants to prove a problem X to be NP-complete,
suffices to take a known NP-complete problem and reduce it to X, by
means of a polynomial-time reduction.


This only shows NP-hardness of X. For NP-completeness, you also have
to show X\in NP.

Yes, I forgot to mention that also X must be in NP-complete.

.

Relevant Pages

  • Re: traveling salesman complexity (exponential, factorial, or something else?)
    ... > Just because one NP-complete problem can be solved in time O) ... > NP is not a time-complexity class. ... NP is polynomial time reducable to a given NP-complete langauge. ... Prev by Date: ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... Qi for all i in, are non-intersecting sets ... Q is an NP-Complete problem ... Then one may conclude that Qi is NP-Complete, for all i in ... "On the Structure of Sets in NP and other Complexity Classes" ...
    (comp.theory)
  • Re: The factoring problem
    ... > in the class NP-complete would be accepted by many as such ... > know there has never been an accepted proof that factoring ... > like an NP-complete problem. ...
    (sci.crypt)
  • Re: Reductions in P
    ... suffices to take a known NP-complete problem and reduce it to X, ... means of a polynomial-time reduction. ... This only shows NP-hardness of X. ...
    (comp.theory)