The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: What is this problem called?
Replies: 3   Last Post: Jul 5, 2005 4:56 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Torben Mogensen

Posts: 60
Registered: 12/6/04
Re: What is this problem called?
Posted: Jul 5, 2005 4:56 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"Russell Easterly" <> writes:

> I have a proof that X3SAT can be converted to subset sum.
> According to Wikipedia, subset sum is NP-Complete.

Note that this isn't a proof that X3SAT is NP-complete -- it just
proves that it is in NP. To prove it is NP-complete, you also need to
show that subset-sum can be reduced to X3SAT.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.