proof of SAT np completeness

65 views Asked by At

I know if we want to prove the np completeness of some problem we must show these :

  • there is a nondeterministic polynomial solution for the problem
  • all other np problems are reducible to the problem in the case of sat problem it's easy to show "there is a nondeterministic polynomial solution for the SAT problem" but I don't know how to prove "all other np problems are reducible to the SAT problem"
1

There are 1 answers

0
Tim On

but I don't know how to prove "all other np problems are reducible to the SAT problem"

This is known as the Cook Levin Theorem: https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem .