Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Menambahkan prana balik Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Tugas pengguna baru: pranala |
Tidak ada ringkasan suntingan |
||
Baris 21:
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.
'''Ide pembuktian:'''
Baris 30 ⟶ 27:
Ide tersebut dapat diilustrasikan pada gambar dibawah ini
Pembuktian:
Baris 49 ⟶ 43:
* Harus terdapat sebuah cell berisi accept state. (φ<sub>accept</sub>)
* Formula:
* φ<sub>cell</sub>: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.
* φ<sub>start</sub>: terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w.
* φ<sub>accept</sub>: minimal 1 cell merupakan accept state
* φ<sub>move</sub> mengecek apakah setiap window 2x3 adalah legal sesuai dengan aturan transisi dari mesin turing.
* Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka:
* sehingga kumpulan dari window legal adalah finite.
* Jika φ satisfiable, maka
* Karena A dapat direduksi menjadi problem SAT dengan input w, dan SAT adalah problem NP, maka terbukti bahwa '''SAT adalah NP-complete'''.
| |||