Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T14:11:46Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 25 Agustus 2026 14.11
Baris 1:		Baris 1:
	Dalam [[Komputasi\|teori kompleksitas komputasi]], '''Teorema Cook-levin''', dikenal juga sebagai '''Teorema Cook''', adalah suatu teori kompleksitas yang dicetuskan oleh Stephen Cook pada Tahun [[1970]] pada seminar nya, dengan judul "The Complexity of Theorem Prooving Procedures". Paper ini memperkenalkan teori NP-completeness yang hingga sekarang menjadi pusat dari teori [[ilmu komputer]].		Dalam [[Komputasi\|teori kompleksitas komputasi]], '''Teorema Cook-levin''', dikenal juga sebagai '''Teorema Cook''', adalah suatu teori kompleksitas yang dicetuskan oleh Stephen Cook pada Tahun [[1970]] pada seminar nya, dengan judul "The Complexity of Theorem Prooving Procedures". Paper ini memperkenalkan teori NP-completeness yang hingga sekarang menjadi pusat dari teori [[ilmu komputer]].
	Teori NP-Completeness ini menyediakan suatu cara untuk mengkategorikan persoalan komputasi yang sulit dengan batas waktu, yaitu jumlah maksimal langkah -langkah yang diperlukan untuk menyelesaikan suatu masalah. Pada paper nya, Cook memaparkan fakta bahwa cukup banyak permasalahan yang sulit untuk diselesaikan tetapi mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu [[polinomial]]).		Teori NP-Completeness ini menyediakan suatu cara untuk mengkategorikan persoalan komputasi yang sulit dengan batas waktu, yaitu jumlah maksimal langkah -langkah yang diperlukan untuk menyelesaikan suatu masalah. Pada paper nya, Cook memaparkan fakta bahwa cukup banyak permasalahan yang sulit untuk diselesaikan tetapi mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu [[polinomial]]).<ref>[http://amturing.acm.org/award_winners/cook_n991950.cfm]</ref>

	Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa:		Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa:
	'''''Problem satisfiability'' (SAT) adalah NP-complete'''		'''''Problem satisfiability'' (SAT) adalah NP-complete'''<ref>[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B Salinan arsip].</ref>

	Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu:		Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu:
	# SAT adalah NP		# SAT adalah NP<ref>[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B Salinan arsip].</ref>
	# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial		# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial<ref>[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B Salinan arsip].</ref>

	Langkah - langkah pembuktian:		Langkah - langkah pembuktian:
Baris 15:		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.		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:		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.'''		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>[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B Salinan arsip].</ref>

	'''Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial'''		'''Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial'''
Baris 59:		Baris 59:

	== Referensi ==		== Referensi ==
			<references />


	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teorema+Cook&oldid=29008398 Wikipedia bahasa Indonesia], revisi 29008398 (2026-03-04T01:57:43Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teorema+Cook&oldid=29008398 Wikipedia bahasa Indonesia], revisi 29008398 (2026-03-04T01:57:43Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29008398; atribusi sumber disertakan.

2026-08-25T13:54:19Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29008398; atribusi sumber disertakan.

Halaman baru

Dalam [[Komputasi|teori kompleksitas komputasi]], '''Teorema Cook-levin''', dikenal juga sebagai '''Teorema Cook''', adalah suatu teori kompleksitas yang dicetuskan oleh Stephen Cook pada Tahun [[1970]] pada seminar nya, dengan judul "The Complexity of Theorem Prooving Procedures". Paper ini memperkenalkan teori NP-completeness yang hingga sekarang menjadi pusat dari teori [[ilmu komputer]].
Teori NP-Completeness ini menyediakan suatu cara untuk mengkategorikan persoalan komputasi yang sulit dengan batas waktu, yaitu jumlah maksimal langkah -langkah yang diperlukan untuk menyelesaikan suatu masalah. Pada paper nya, Cook memaparkan fakta bahwa cukup banyak permasalahan yang sulit untuk diselesaikan tetapi mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu [[polinomial]]).

Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa:
'''''Problem satisfiability'' (SAT) adalah NP-complete'''

Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu:
# SAT adalah NP
# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial

Langkah - langkah pembuktian:
'''SAT adalah NP'''
SAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi ''satisfiablility'' dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah [[Mesin Turing|mesin turing]] deterministik.
contoh: E = (X1 V ¬X1 V X2) Ʌ (X3 V X2 V ¬X1) Ʌ (X1 V X2) Ʌ (X3)
dengan memberikan assignment pada variabel X1, X2, X3. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True.
Misal diberikan nilai:
X1 =T, X2 = T, X3 = 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.'''

'''Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial'''
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:'''
* Untuk setiap A adalah NP, dengan input w, menghasilkan sebuah formula boolean φ yang menyimulasikan mesin turing menghasilkan A pada input w.
* Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable.

Ide tersebut dapat diilustrasikan pada gambar dibawah ini

Pembuktian:
* Asumsi:
:w : input
:A : language
:N : mesin turing NP yang menentukan A
:N menentukan w∈anggota A dalan nk langkah untuk constanta k
* Sebuah variable dapat dinyatakan dalam Xi,j,s
* Xi,j,s: true jika cell [i,j] bernilai s; selain itu bernilai false
* cell[i,j]: cell dengan lokasi baris ke-i dan kolom ke -j
* Suatu Tableau tanpa aturan tertentu dapat berisi konfigurasi yang invalid, misal: cell berisi ''multiple symbols'', tidak dimulai dengan input w dan state q0, konfigurasi neighbour tidak berkorespondensi dengan aturan transisi, dan sebagainya. Sehingga harus dihasilkan formula Boolean yang memaksa tableau agar valid dan menghasilkan ''result'' pada ''accet state''.
* Sebuah cell dapat berisi tepat 1 symbol di antara sebuah state, sebuah alphabet tape, dan sebuah #. (φ cell)
* Konfigurasi pertama harus berhubungan dengan input w dan state awal q. (φ start)
* Sebuah konfigurasi diturunkan dari konfigurasi sebelumnya sesuai dengan aturan transisi pada mesin turing. (φmove)
* Harus terdapat sebuah cell berisi accept state. (φaccept)
* Formula:

* φcell: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.

* φstart: terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w.

* φaccept: minimal 1 cell merupakan accept state

* φmove 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'''.

== Referensi ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teorema+Cook&oldid=29008398 Wikipedia bahasa Indonesia], revisi 29008398 (2026-03-04T01:57:43Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Teorema Cook - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29008398; atribusi sumber disertakan.