เกี่ยวกับปัญหา P กับ NP

ปัญหานี้เป็นปัญหาเชิงทฤษฎีที่สำคัญที่สุดและโด่งดังที่สุดของวิทยาการคอมพิวเตอร์ หลายคนบอกว่าวิทยาการคอมพิวเตอร์เชิงทฤษฎีไม่สามารถจะพูดเกี่ยวกับผลงานของสาขาตนเองได้มากนัก เพราะแม้แต่ปัญหาที่เป็นพื้นฐานที่สุด เรายังไม่สามารถตอบได้เลย

สำหรับคนที่เคยผ่านหูผ่านตาปัญหาชื่อประมาณนี้มาบ้าง ขอผมทบทวนสักหน่อยโดยใช้ภาษาที่ไม่เป็นทางการนัก

เวลาผมกล่าวถึง "ปัญหา" ผมหมายถึงปัญหาที่ต้องการคำตอบว่า "ใช่" หรือ "ไม่ใช่" เช่น ปัญหาจำนวนเฉพาะ ที่ให้จำนวนเต็มบวกมาหนึ่งจำนวน แล้วถามว่าจำนวนหนึ่งเป็นจำนวนเฉพาะหรือไม่?

• ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา P คือปัญหาที่เรามีวิธีที่หาคำตอบได้อย่างมีประสิทธิภาพ
• ปัญหาที่ถูกจัดอยู่ในกลุ่มปัญหา NP คือปัญหาที่ถ้าคำตอบของปัญหาหนึ่ง ๆ คือใช่ เรามีวิธีการที่จะยืนยันคำตอบนั้นอย่างมีประสิทธิภาพ
  

(อ่านเพิ่มที่วิกิพีเดียไทย)

ปัญหานี้เป็นเรื่องพื้นฐานมาก ๆ ของการหาคำตอบ กับการยืนยันคำตอบ ซึ่งหลาย ๆ คนเชื่อกันว่า อย่างหลังน่าจะง่ายกว่า

ผมจำได้ว่าได้อ่านจาก โพล ที่ทำโดย William Gasarch เกี่ยวกับปัญหา P และ NP คำตอบหนึ่งของ Luca Trevisan ในโพลนั้น (ที่หลาย ๆ คนคงคิดคล้าย ๆ กับเขา) ก็คือ เขากลัวว่าการพิสูจน์ปัญหาดังกล่าวจะเกิดจากการที่บางคนสังเกตเห็นความเกี่ยวข้องบางอย่างระหว่างปัญหานี้กับคณิตศาสตร์แปลก ๆ แล้วก็พิสูจน์ปัญหานี้ออกมาโดยการทำงานในคณิตศาสตร์แปลก ๆ นั้น แล้วเราซึ่งเป็นนักวิทยาการคอมพิวเตอร์ซึ่งรู้เรื่องแค่คอมบินาทอริคส์ จะไม่มีทางเข้าใจบทพิสูจน์นั้นเลย

(ผมได้ข่าวจากบล็อกของ Luca) ในงานการประชุมนักคณิตศาสตร์นานาชาติที่กรุงมาดริก (ICM'06) ที่จะถึงนี้ Avi Wigderson จะนำเสนอบทความ ที่สรุปความคืบหน้าของการพิสูจน์ปัญหา P กับ NP ตอนต้นบทความเขาอ้างถึงคำพูดของ Steve Smale ว่า "ปัญหา P กับ NP --- ของขวัญสำหรับคณิตศาสตร์จากวิทยาการคอมพิวเตอร์"

เราอาจได้เห็นความคืบหน้าบางอย่าง และสิ่งที่ Luca กลัวที่สุดอาจเป็นจริงก็ได้