Klaim Peneliti HP untuk Crack Compsci Complexity Conundrum

Sementara Hewlett-Packard mengambil dari kejatuhan CEO-nya Mark Hurd mundur, perusahaan dapat berjemur dalam kejayaan setidaknya satu pencapaian yang berpotensi positif: Seorang peneliti HP telah menawarkan apa yang dia katakan sebagai solusi untuk salah satu masalah yang paling sulit dalam ilmu komputer.

Ilmuwan riset utama HP Labs, Vinay Deolalikar, telah memposting apa yang dia klaim sebagai solusi untuk apa yang secara luas dikenal sebagai masalah P versus NP.

Begitu sulitnya masalah ini bahwa Clay Mathematics Institute telah bersumpah untuk memberikan penghargaan kepada orang yang memecahkannya. $ 1 juta. Ini adalah salah satu dari hanya tujuh masalah, yang secara kolektif dikenal sebagai Masalah Hadiah Milenium, lembaga ini telah menawarkan karunia ini. Salah satu dari tujuh, dugaan Poincaré, secara resmi dipecahkan pada tahun 2006.

Belum jelas apakah Deolalikar akan mendapatkan uang tunai, karena Clay belum mengatakan bahwa masalah ini dipecahkan.

Masalah ini, "salah satu dari masalah yang luar biasa dalam ilmu komputer, "melibatkan" menentukan apakah ada pertanyaan yang jawabannya dapat dengan cepat diperiksa, tetapi yang membutuhkan waktu sangat lama untuk dipecahkan dengan prosedur langsung, "halaman Institute menjelaskan. Dalam masalah, P singkatan untuk waktu polinomial dan NP adalah kependekan dari waktu polinomial yang tidak jelas.

"Saya senang mengumumkan bukti bahwa P tidak sama dengan NP," Deolalikar mengumumkan dalam sebuah email kepada sekelompok profesor matematika, yang kemudian diposting pada hari Minggu oleh Greg Baker, seorang dosen senior di British Columbia Simon Fraser University.

Singkatnya, ini mungkin berarti bahwa masalah-masalah tertentu hanya dapat diselesaikan dengan pencarian kasar, jika solusi dapat ditemukan di semua.

"Buktinya diperlukan penyambungan bersama prinsip-prinsip dari berbagai bidang dalam matematika. Upaya utama dalam membangun bukti ini adalah mengungkap rantai hubungan konseptual antara berbagai bidang dan melihatnya melalui lensa umum," tulis Deolalikar.

Tentu saja, mereka yang memiliki pengetahuan dengan masalah ragu-ragu untuk menyatakan bahwa Deolalikar telah memecahkan masalah, mengingat jumlah pemeriksaan yang perlu dilakukan. Dan sementara mereka memuji Deolalikar untuk pendekatannya yang menyeluruh, yang berbeda dari dugaan yang lebih serampangan yang biasanya disajikan, tidak ada yang secara pasti mengklaim bahwa dia telah memecahkan masalah.

"Sepertinya memperkenalkan beberapa ide baru pemikiran, khususnya hubungan antara fisika statistik dan karakterisasi logika orde pertama dari NP, "tulis Scott Aaronson, asisten profesor teknik elektro dan ilmu komputer di Massachusetts Institute of Technology, dalam entri blog nonkomittal.

" Saya tidak tahu apa untuk berpikir sekarang, tapi saya pasti berharap, "tulis Dick Lipton, seorang profesor ilmu komputer di Institut Teknologi Georgia.

Joab Jackson mencakup perangkat lunak perusahaan dan teknologi umum untuk berita The IDG News Service. Ikuti Joab di Twitter di @Joab_Jackson. Alamat e-mail Joab adalah [email protected]