Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Np-completeness; Cook's Theorem

  1. Jan 29, 2005 #1
    I must say that the various proofs of this theorem are really difficult to absorb. I'll probably have more than a few questions about them. Meanwhile, I found a SUNY-Stony Brook website that seemed like a useful reference, but it includes the following statement which I think says exactly the opposite of what it should say:
    Isn't that backwards? To be precise, we must show that every problem in NP is polynomial time reducible to SAT. So, to paraphrase that in a more colloquial way, wouldn't it be more accurate to say that we must show that SAT is at least as hard as any problem in NP?
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted

Similar Discussions: Np-completeness; Cook's Theorem
  1. SAT is NP-complete (?) (Replies: 10)

  2. Problems in NP (Replies: 5)

  3. Completeness theorem (Replies: 3)

  4. P vs NP and factoring (Replies: 3)