Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
kTidak ada ringkasan suntingan |
kTidak ada ringkasan suntingan |
||
Baris 11:
Langkah - langkah pembuktian :
'''
SAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi satisfiabliity dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah mesin turing deterministik.
contoh : E = (X<sub>1</sub> V ¬X<sub>1</sub> V X<sub>2</sub>) Ʌ (X<sub>3</sub> V X<sub>2</sub> V ¬X<sub>1</sub>) Ʌ (X<sub>1</sub> V X<sub>2</sub>) Ʌ (X<sub>3</sub>)
Baris 18:
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.'''
dapat dinyatakan dalam bentuk sebagai berikut : pict1
Akan diperlihatkan bahwa untuk setiap A ∈ NP dengan input w, sangat dimungkinkan untuk menghasilkan sebuah formula Boolean yag satisfiable jika w anggota A.
Baris 25:
</gallery>
'''Ide pembuktian :'''
* Untuk setiap A adalah NP, dengan input w, menghasilkan sebuah formula boolean φ yang mensimulasikan mesin turing menghasilkan A pada input w.
* Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable.
| |||