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

2026-08-25T04:08:32Z

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

← Revisi sebelumnya		Revisi per 25 Agustus 2026 04.08
Baris 1:		Baris 1:
			[[File:Complexity_classes.svg\|thumb\|right\|280px\|Complexity classes]]

	'''Masalah P versus NP''' adalah permasalahan besar yang merupakan salah satu [[Daftar masalah yang belum terpecahkan computer science\|masalah yang belum terpecahkan dalam bidang ilmu komputer]]. Problema ini menanyakan apakah setiap masalah yang solusinya dapat segera diverifikasi (secara teknis, diverifikasi dalam [[waktu polinomial]]) juga dapat dipecahkan dengan cepat (sekali lagi, dalam waktu polinomial).		'''Masalah P versus NP''' adalah permasalahan besar yang merupakan salah satu [[Daftar masalah yang belum terpecahkan computer science\|masalah yang belum terpecahkan dalam bidang ilmu komputer]]. Problema ini menanyakan apakah setiap masalah yang solusinya dapat segera diverifikasi (secara teknis, diverifikasi dalam [[waktu polinomial]]) juga dapat dipecahkan dengan cepat (sekali lagi, dalam waktu polinomial).

	Isu yang mendasari masalah ini pertama kali dibahas pada tahun 1950-an, dalam surat dari [[John Forbes Nash Jr.]] ke [[National Security Agency]], dan dari [[Kurt Gödel]] ke [[John von Neumann]]. Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh [[Stephen Cook]] dalam ''paper'' seminarnya "Kompleksitas prosedur pembuktian teorema" dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang [[ilmu komputer]]. Problema ini adalah salah satu dari tujuh [[Masalah Milenium]] yang dipilih [[Clay Mathematics Institute]] untuk membawa hadiah senilai US $ 1.000.000 bagi pencetus solusi pertama yang benar.		Isu yang mendasari masalah ini pertama kali dibahas pada tahun 1950-an, dalam surat dari [[John Forbes Nash Jr.]] ke [[National Security Agency]], dan dari [[Kurt Gödel]] ke [[John von Neumann]]. Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh [[Stephen Cook]] dalam ''paper'' seminarnya "Kompleksitas prosedur pembuktian teorema"<ref>Stephen Cook. ''Proceedings of the Third Annual ACM Symposium on Theory of Computing''. 1971. hlm. 151–158.</ref> dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang [[ilmu komputer]].<ref>Lance Fortnow. [http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf The status of the '''P''' versus '''NP''' problem]. ''Communications of the ACM''. 2009. Vol. 52 (9). hlm. 78–86. doi:10.1145/1562164.1562186.</ref> Problema ini adalah salah satu dari tujuh [[Masalah Milenium]] yang dipilih [[Clay Mathematics Institute]] untuk membawa hadiah senilai US $ 1.000.000 bagi pencetus solusi pertama yang benar.

	Istilah informal ''dengan cepat'', yang digunakan di atas, berarti adanya algoritma yang memecahkan tugas yang berjalan dalam [[waktu polinom]], sehingga waktu untuk menyelesaikan tugas bervariasi sebagai fungsi polinom pada ukuran input ke algoritma (berlawanan dengan, katakanlah, [[waktu eksponensial]]). Kelas umum pertanyaan yang beberapa algoritmanya dapat memberikan jawaban dalam waktu polinomial disebut "kelas '''P'''" atau hanya "'''[[P (kompleksitas)\|P]]'''". Untuk beberapa pertanyaan, tidak ada cara yang diketahui untuk menemukan jawaban dengan cepat, tetapi jika ada informasi yang menunjukkan jawabannya, mungkin untuk memverifikasi jawabannya dengan cepat. Kelas pertanyaan yang jawabannya dapat '' diverifikasi '' dalam waktu polinom disebut '''[[NP (kompleksitas)\|NP]]''', yang berarti "waktu polinomial nondeterministik".		Istilah informal ''dengan cepat'', yang digunakan di atas, berarti adanya algoritma yang memecahkan tugas yang berjalan dalam [[waktu polinom]], sehingga waktu untuk menyelesaikan tugas bervariasi sebagai fungsi polinom pada ukuran input ke algoritma (berlawanan dengan, katakanlah, [[waktu eksponensial]]). Kelas umum pertanyaan yang beberapa algoritmanya dapat memberikan jawaban dalam waktu polinomial disebut "kelas '''P'''" atau hanya "'''[[P (kompleksitas)\|P]]'''". Untuk beberapa pertanyaan, tidak ada cara yang diketahui untuk menemukan jawaban dengan cepat, tetapi jika ada informasi yang menunjukkan jawabannya, mungkin untuk memverifikasi jawabannya dengan cepat. Kelas pertanyaan yang jawabannya dapat '' diverifikasi '' dalam waktu polinom disebut '''[[NP (kompleksitas)\|NP]]''', yang berarti "waktu polinomial nondeterministik".<ref>Mesin Turing nondeterministik dapat beralih ke keadaan yang tidak ditentukan oleh keadaan sebelumnya. Mesin seperti itu bisa memecahkan masalah NP pada waktu polinomial dengan masuk ke keadaan jawaban yang benar (dengan keberuntungan), kemudian secara konvensional memverifikasinya. Mesin seperti itu tidak praktis untuk memecahkan masalah realistis tetapi bisa dijadikan model teoretis.</ref>

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

			== Sumber dan atribusi ==

			Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Masalah+P+versus+NP&oldid=28481055 Wikipedia bahasa Indonesia], revisi 28481055 (2025-11-14T07:21:40Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

	~~== Sumber dan atribusi ==~~		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

	~~Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Masalah+P+versus+NP&oldid=28481055 Wikipedia bahasa Indonesia], revisi 28481055 (2025~~-11-~~14T07:21:40Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi~~-~~BerbagiSerupa (CC BY~~-~~SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.~~

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

2026-08-25T03:41:25Z

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

Halaman baru

'''Masalah P versus NP''' adalah permasalahan besar yang merupakan salah satu [[Daftar masalah yang belum terpecahkan computer science|masalah yang belum terpecahkan dalam bidang ilmu komputer]]. Problema ini menanyakan apakah setiap masalah yang solusinya dapat segera diverifikasi (secara teknis, diverifikasi dalam [[waktu polinomial]]) juga dapat dipecahkan dengan cepat (sekali lagi, dalam waktu polinomial).

Isu yang mendasari masalah ini pertama kali dibahas pada tahun 1950-an, dalam surat dari [[John Forbes Nash Jr.]] ke [[National Security Agency]], dan dari [[Kurt Gödel]] ke [[John von Neumann]]. Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh [[Stephen Cook]] dalam ''paper'' seminarnya "Kompleksitas prosedur pembuktian teorema" dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang [[ilmu komputer]]. Problema ini adalah salah satu dari tujuh [[Masalah Milenium]] yang dipilih [[Clay Mathematics Institute]] untuk membawa hadiah senilai US $ 1.000.000 bagi pencetus solusi pertama yang benar.

Istilah informal ''dengan cepat'', yang digunakan di atas, berarti adanya algoritma yang memecahkan tugas yang berjalan dalam [[waktu polinom]], sehingga waktu untuk menyelesaikan tugas bervariasi sebagai fungsi polinom pada ukuran input ke algoritma (berlawanan dengan, katakanlah, [[waktu eksponensial]]). Kelas umum pertanyaan yang beberapa algoritmanya dapat memberikan jawaban dalam waktu polinomial disebut "kelas '''P'''" atau hanya "'''[[P (kompleksitas)|P]]'''". Untuk beberapa pertanyaan, tidak ada cara yang diketahui untuk menemukan jawaban dengan cepat, tetapi jika ada informasi yang menunjukkan jawabannya, mungkin untuk memverifikasi jawabannya dengan cepat. Kelas pertanyaan yang jawabannya dapat '' diverifikasi '' dalam waktu polinom disebut '''[[NP (kompleksitas)|NP]]''', yang berarti "waktu polinomial nondeterministik".

== Referensi ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Masalah+P+versus+NP&oldid=28481055 Wikipedia bahasa Indonesia], revisi 28481055 (2025-11-14T07:21:40Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Masalah P versus NP - Riwayat revisi

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

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