ไม่ได้มาเขียนบทความซะหลายวัน พอดีช่วงนี้งานยุ่งจริงๆครับ หลายวันก่อนผู้เขียนได้เกริ่นถึง The Millennium Problems ไปบ้างแล้ว แต่ไม่ได้ชี้แจงถึงรายละเอียดของปัญหาแต่ละข้อให้ ในบทความนี้จะพูดถึงปัญหาข้อแรก ปัญหาข้อนี้เป็นปัญหาที่สำคัญที่สุดของเหล่าโปรแกรมเมอร์ก็ว่าได้ ปัญหาข้อนี้มีชื่อว่า P vs NP เนื่องจากเนื้อหาของปัญหาเหล่านี้ค่อนค่างจะลึกซึ้ง จะพยายามอธิบายให้เข้าใจพอมองเห็นภาพรวมของปัญหาข้อนี้
ปัญหา P vs NP แทบจะกล่าวได้ว่าเป็นปัญหาที่สำคัญที่สุดในวงการนักเขียนโปรแกรม เพราะโปรแกรมถึงจะดีขนาดไหน แต่ถ้าทำงานช้ายืดยาดเหลือเกิน ก็คงไม่มีใครอยากใช้ นักคอมพิวเตอร์จึงต้องจัดประเภทของรูปแบบของงานตามความเร็วที่คอมพิวเตอร์จะสามารถทำได้
"P" (Polynomial time) คือรูปแบบงานที่คอมพิวเตอร์ทำได้เร็ว
"E" (Exponential time) คือรูปแบบงานที่ต้องใช้เวลามาก
แต่รูปแบบงานทั่วไปของโรงงานอุตสาหกรรมห้างร้านทั้งหลาย ยากกว่าแบบ P แต่ก็ไม่ได้ยากเหมือนแบบ E จึงอยู่ตรงกลางและได้ชื่อว่ามีรูปแบบ "NP" (Nondeterministic Polynomial time) แต่ก็มีความเชื่อที่ว่างานในรูปแบบ NP นั้น ในความเป็นจริงอาจจะง่ายเหมือนอย่างงานในรูปแบบ P ก็ได้ เพียงแต่ยังไม่มีใครรู้วิธีเท่านั้นเอง
"ถ้าจะมีเครื่องคิดเลขสักเครื่องแล้วคนคนหนึ่งอยากรู้ว่า 3329 คูณ 4547 ได้เท่าไหร่ กดเครื่องคิดเลขแปบเดียวก็ตอบได้แล้วว่าผลลัพท์คือ 15136963 ถ้าจะมีคนอีกคนหนื่งอยากรู้ว่า 15136963 เท่ากับเลขใดคูณกัน เขาอาจต้องใช้เวลาเป็นวันๆในการกดเครื่องคิดเลขไล่ไปเรื่อยๆ การ "คูณ" นั้น สำหรับคอมพิวเตอร์แล้วเป็นงานที่ง่าย เป็นงานในรูปแบบ P แต่การ "แยกตัวประกอบ" นั้นเป็นงานที่ยาก เป็นงานในรูปแบบ NP แต่ทั้งนี้ ไม่มีใครแน่ใจว่า "งานที่ยาก" นั้น ยากโดยตัวของมันเอง หรือยากเพราะมนุษย์เรายังไม่รู้วิธีจัดการที่เหมาะสม"
คำถามคือจริงหรือไม่ที่งานในรูปแบบ NP ง่ายเหมือนในรูปแบบ P
ปัญหา P vs NP จึงเป็นเหมือนคำถามซ้อนคำถาม เพราะ P และ NP เองที่จริงก็คือรูปแบบของคำถามนี่เอง นักวิจัยส่วนที่เชื่อว่า P = NP จะหาวิธีแก้ปัญหาในรูปแบบ NP ให้เร็วขึ้น หากทำได้จริง คอมพิวเตอร์จะสามารถทำงานได้เร็วขึ้น
เสน่ห์อย่างหนึ่งของโจทย์ปัญหาข้อนี้ก็คือ หาก P = NP จริง การพิสูจน์ว่า P = NP จะสามารถทำได้โดยใช้ความคิดสร้างสรรค์ล้วนๆไม่ต้องใช้คณิตศาสตร์เลย หากจะมีเด็กประถมสมองใส หาวิธีการทำงานหนึ่งงานใดในรูปแบบ NP - complete ให้เสร็จอย่างรวดเร็วได้ ก็จะได้ชื่อว่าพิชิตปัญหา P vs NP แล้ว จะอย่างไรก็ดี แม้แต่ผู้เชี่ยวชาญที่ทุ่มเทเวลาให้กับงานวิจัยก็ยังไม่พบวิธีแก้ปัญหา
