Masalah Milenium
Diagram kelas kompleksitas menyatakan P ≠ NP. Adanya masalah di dalam NP tapi di luar keduanya P dan NP-lengkap, asumsi tersebut, didasarkan pada Teorema Ladner.[1]

Masalah P versus NP adalah permasalahan besar yang merupakan salah satu 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"[2] dan dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang ilmu komputer.[3] 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". 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, yang berarti "waktu polinomial nondeterministik".[4]

Referensi

sunting
  1. ^ R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
  2. ^ Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. hlm. 151–158. ;
  3. ^ Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF). Communications of the ACM. 52 (9): 78–86. doi:10.1145/1562164.1562186.
  4. ^ 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.


Ikon rintisan

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

📚 Artikel Terkait di Wikipedia

Keberadaan dan kemulusan Navier–Stokes

Navier–Stokes existence and smoothness (Millennium Prize Problem) A lecture on the problem by Luis Caffarelli. "Navier Stokes Equation – A Million-Dollar

Konjektur Hodge

ataupun menyangkal konjektur Hodge. The Clay Math Institute Official Problem Description by P. Deligne (pdf) Popular lecture on Hodge Conjecture by Dan Freed

Algoritma

masalah masih menjadi pertanyaan terbukan yang dikenal sebagai Masalah P versus NP. Ada dua kelas besar dari algoritma ini: Algoritma Monte Carlo mengembalikan

Keberadaan Yang–Mills dan celah massa

teori ini. Arthur Jaffe and Edward Witten "Quantum Yang-Mills theory. Diarsipkan 2015-03-30 di Wayback Machine." Official problem description. l b s

Kalium

Moore-Ede, M. C. (1986). "Physiology of the circadian timing system: predictive versus reactive homeostasis". Am J Physiol. 250: R737 – R752. Slonim, Anthony D

Matematika

masalah terbuka yang mendasar. Yang paling terkenal adalah "Masalah P versus NP", salah satu Masalah Milenium. Matematika terapan berkenaan dengan penggunaan

Hipotesis Riemann

R. Acad. Sci. Paris, 158: 1979–1981 Beurling, Arne (1955), "A closure problem related to the Riemann zeta-function", Proceedings of the National Academy

Daftar masalah matematika yang belum terpecahkan

tersebut. Keenam masalah yang masih belum terpecahkan adalah: Masalah P versus NP Konjektur Hodge Hipotesis Riemann Keberadaan Yang–Mills dan celah massa