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 Threads - completeness Cook's Theorem Date
I An easy proof of Gödel's first incompleteness theorem? Mar 6, 2018
Lattice/Complete lattice Jun 10, 2014
Confidence of complete spatial randomness May 8, 2014
Complete Random Design vs RCBD Sep 7, 2013
Completeness notions in logic Feb 23, 2013