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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

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