นักวิจัย HP กำลังจะตีพิมพ์บทพิสูจน์ P != NP

Submitted by lew on Mon, 09/08/2010 - 09:32

Vinay Deolalikar นักวิจัยจากห้องปฎิบัติการวิจัย HP อ้างว่าได้ใช้เวลาส่วนตัวเพื่อพิสูจน์ว่า P (ปัญหาที่แก้ได้ในเวลา polynomial) ไม่เท่ากับ NP (non-polynomial) เป็นผลสำเร็จหลังจากที่พยายามหลายครั้งในช่วงเวลาสองปีที่ผ่านมา

เอกสารความยาว 102 หน้ากระดาษ (Scribd) แสดงบทพิสูจน์ โดย Deolalikar ได้อีเมลรายงานนี้ออกไปให้นักวิจัยอื่นๆ ในวันที่ 6 ที่ผ่านมา และเขาอ้างในเว็บของเขาว่าเริ่มได้รับคำยืนยันบทพิสูจน์นี้ในวันที่ 8 ที่ผ่านมา

P != NP (หรือ P == NP) เป็นหนึ่งในเจ็ดปัญหาล้านดอลลาร์ของสถาบันคณิตศาสตร์ Clay ที่จนทุกวันนี้มีปัญหาเพียงข้อเดียวที่ถูกพิสูจน์ไปแต่นักวิจัยกลับปฏิเสธการรับรางวัล

ก่อนที่จะได้รับรางวัลนั้นปรกติจะต้องรอจนรายงานการยืนยันบทพิสูจน์ได้รับการตีพิมพ์ ในกรณี Poincaré conjecture นั้นได้รับการยืนยันเป็นทางการสามครั้งก่อนจะมีการติดต่อเพื่อมอบรางวัล

ที่มา - Greg and Kat's Blog