HP Researcher Claims to Crack Compsci Complexity Conundrum

Sementara Hewlett-Packard geli dari kejatuhan Ketua Pegawai Eksekutifnya, Mark Hurd melangkah ke bawah, syarikat itu boleh membuat kemuliaan sekurang-kurangnya satu pencapaian yang berpotensi positif: Seorang penyelidik HP telah menawarkan apa yang dikatakannya adalah penyelesaian kepada salah satu masalah paling sukar dalam sains komputer.

Saintis penyelidikan utama Makmal HP, Vinay Deolalikar telah memposting apa yang dikatakannya adalah penyelesaian kepada apa yang dikenali sebagai masalah NP versus P.

Jadi tidak dapat dipertimbangkan adalah masalah ini yang Institut Matematik Clay telah bersumpah untuk memberi penghargaan kepada orang yang menyelesaikannya AS $ 1 juta. Ini adalah salah satu daripada tujuh masalah, secara kolektif dikenali sebagai Masalah Hadiah Milenium, institut telah menawarkan hadiah ini. Salah satu daripada tujuh, ramalan Poincaré, telah diselesaikan secara rasmi pada tahun 2006.

Tidak jelas lagi jika Deolalikar akan mendapat wang tunai, kerana Clay tidak mengatakan bahawa ia menganggap masalah diselesaikan.

Masalah ini, "salah satu daripada masalah luar biasa dalam sains komputer, "melibatkan" menentukan sama ada soalan wujud yang jawapannya boleh diperiksa dengan cepat, tetapi memerlukan masa yang lama untuk menyelesaikan dengan sebarang prosedur langsung, "jelas halaman Institut. Dalam masalah itu, P bermaksud masa polinom dan NP adalah untuk masa polinomial nondeterministik.

"Saya gembira untuk mengumumkan bukti bahawa P tidak sama dengan NP," Deolalikar mengumumkan dalam e-mel kepada sekumpulan profesor matematik, yang kemudiannya diposting pada hari Ahad oleh Greg Baker, pensyarah kanan di British Columbia, Universiti Simon Fraser.

Secara ringkasnya, ini mungkin bermakna bahawa masalah tertentu hanya dapat diselesaikan oleh pencarian kasar, jika penyelesaian dapat dijumpai di semua "

" bukti itu memerlukan prinsip-prinsip dari beberapa bidang dalam matematik. Usaha utama dalam membuktikan bukti ini ialah mencari rangkaian rangkaian konsep antara pelbagai bidang dan melihatnya melalui lensa biasa, "tulis Deolalikar.

Secara semula jadi, mereka yang berpengetahuan dengan masalah itu teragak-agak untuk menyatakan bahawa Deolalikar telah menyelesaikan masalah itu, memandangkan jumlah pemeriksaan yang perlu dilakukan. Dan sementara mereka memuji Deolalikar untuk pendekatannya yang menyeluruh, satu yang berbeza dari tebakan yang lebih serasi yang biasanya dipersembahkan, tidak ada yang mengaku telah memecahkan masalah itu.

"Nampaknya memperkenalkan beberapa ide baru yang mendorong pemikiran, khususnya hubungan antara fizik statistik dan pencirian logik urutan pertama NP, "tulis Scott Aaronson, penolong profesor kejuruteraan elektrik dan sains komputer di Massachusetts Institute of Technology, dalam entri blog yang tidak berpengalaman.

" Saya tidak tahu apa untuk berfikir sekarang, tetapi saya sememangnya berharap, "tulis Dick Lipton, seorang profesor sains komputer di Institut Teknologi Georgia.

Joab Jackson merangkumi perisian perusahaan dan berita teknologi umum untuk Perkhidmatan Berita IDG. Ikut Joab di Twitter di @Joab_Jackson. Alamat e-mel Joab ialah [email protected]