Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
Tidak ada ringkasan suntingan |
||
Baris 15:
dengan memberikan assignment pada variabel X<sub>1</sub>, X<sub>2</sub>, X<sub>3</sub>. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True.
Misal diberikan nilai :
X<sub>1</sub> =T , X<sub>2</sub> = T, X<sub>3</sub> = T, maka ekspresi akan bernilai True. Untuk mengecek suatu problem SAT dengan memberikan nilai pada variabel, dapat diselesaikan dalam waktu polinomial, sehingga '''SAT adalah NP.''' <ref name="ww"/>
'''Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial'''
| |||