P versus NP problem
หนึ่งในปัญหาที่แก้แล้วได้เงินล้านดอลลาร์สหรัฐฯ
สิ่งประดิษฐ์ที่เรียกว่าคอมพิวเตอร์นั้นเปลี่ยนแปลงวิถีชีวิตมนุษย์ไปอย่างมาก
มันช่วยให้ชีวิตมนุษย์เราง่ายขึ้น แทนที่เราต้องคำนวณทุกอย่างด้วยสมอง เราก็ให้คอมพิวเตอร์ (หรือ เครื่องคิดเลข ซึ่งก็คือคอมพิวเตอร์อย่างง่าย) คำนวณแทน
ไม่น่าแปลกใจที่
ปัญหาทางคณิตศาสตร์จะถูกแบ่งประเภทโดยใช้คอมพิวเตอร์เป็นศูนย์กลางด้วย
ปัญหาในมุมมองของคอมพิวเตอร์แบ่งได้หลายประเภท* แต่ในที่นี้จะสนใจ 2 ประเภท นั่นคือ
ปัญหาประเภท P และ ปัญหาประเภท NP
ปัญหาสองกลุ่มนี้เองเป็นบ่อเกิดของหนึ่งใน 7 ปัญหาสุดยากที่สถาบันคณิตศาสตร์เคลย์ (Clay Mathematics Institute) ประกาศไว้เมื่อปี ค.ศ. 2000 ว่าหากใครแก้ได้จะได้เงิน 1 ล้านเหรียญสหรัฐฯ
ปัญหาดังกล่าวมีชื่อว่า P versus NP problem
ซึ่งสามารถทำความเข้าใจได้ทีละส่วนดังนี้
1. ปัญหาประเภท P เป็นปัญหาที่เราหาคำตอบได้เร็ว และสามารถตรวจคำตอบได้เร็ว
ยิ่งเป็นคอมพิวเตอร์ก็ยิ่งเร็วไปกันใหญ่
ปัญหาเหล่านี้เมื่อได้คำตอบแล้วก็สามารถตรวจความถูกต้องได้ไม่ยาก เช่น การบวก ลบ คูณ หาร , การเรียงลำดับเลข (Sorting) ฯลฯ
ถ้ามีเลขมา 5 จำนวน เช่น 5 , 102 , 67, 11, 64
มีวิธีมากมายที่ใช้ในการเรียงเลขจากน้อยไปหามากซึ่งจะได้คำตอบเป็น (5 , 11 , 64 , 67, 102) ซึ่งเวลาตรวจคำตอบก็แค่ไล่เรียงไปทีละจำนวนอย่างไม่ยากเย็นอะไร
ถ้าขนาดของปัญหาประเภท P ใหญ่ขึ้น
เวลาที่ต้องใช้ก็จะมากขึ้นตามไปด้วยซึ่งการเพิ่มขึ้นของเวลานั้น ไม่ได้เพิ่มอย่างรวดเร็วนัก แต่เพิ่มด้วยลักษณะทางคณิตศาสตร์ที่เรียกว่า polynomial time
การแก้ปัญหาประเภทนี้จึงไม่เป็นปัญหาอะไรมาก
2.ปัญหาประเภท NP เป็นปัญหาที่ใช้เวลานานในการแก้
แต่ถ้ามีคำตอบอยู่ในมือแล้ว จะใช้เวลาตรวจคำตอบไม่นานเลย เช่น การแยกตัวประกอบ (Prime factorization), การเล่นเกมซุโดกุ (Sudoku) ฯลฯ
การแยกตัวประกอบจำนวน 15,900,011 ให้อยู่ในรูปจำนวนเฉพาะ นั้นทำได้ยากมาก ยิ่งจำนวนมีค่ามากก็ยิ่งใช้เวลานานในการแก้ปัญหาแบบพุ่งกระฉูด
แต่หากให้คำตอบมาว่า 7,883 กับ 2,017
เราสามารถคูณเลขสองตัวนี้กลับเพื่อทดสอบได้อย่างรวดเร็วกว่ามันเป็นตัวประกอบของจำนวนนั้นจริงหรือไม่
ปัญหาคือ ในโลกคณิตศาสตร์มีปัญหาประเภท NP อยู่เป็นจำนวนมาก ที่น่าสนใจ
ทว่ามันต้องใช้เวลาในการแก้นานมาก
นักคณิตศาสตร์ต้องการจะแก้ปัญหาประเภท NP ให้ได้อย่างรวดเร็วแบบปัญหาประเภท P
แต่ยังไม่สามารถทำได้
นักคณิตศาสตร์จำนวนเชื่อว่าทำได้ แต่นักคณิตศาสตร์อีกจำนวนหนึ่งเชื่อว่าไม่มีทางทำได้
นี่คือปัญหา P versus NP problem
นั่นคือ เราจะสามารถพิสูจน์ให้เห็นได้หรือไม่ว่าปัญหาประเภท NP ถูกแก้ได้อย่างรวดเร็วไม่ต่างจากปัญหาประเภท P
หากปัญหานี้ถูกไขไม่ว่าทางใดก็ย่อมสร้างความเปลี่ยนแปลงให้กับโลกคณิตศาสตร์และวิทยาการคอมพิวเตอร์อย่างยิ่งเพราะถ้าสามารถพิสูจน์ว่าทำได้ ย่อมมีการระดมสรรพกำลังสติปัญญาหาทางเหล่านั้น ซึ่งถ้าทางออกเหล่านั้นปรากฏขึ้นจะส่งผลต่อชีวิตประจำวันเราอย่างมาก เพราะการแยกตัวประกอบนั้นเกี่ยวข้องกับการเข้ารหัส ฯลฯ
กระนั้น ถ้าพิสูจน์ว่าถึงอย่างไรก็ทำไม่ได้ นักคณิตศาสตร์จะได้เอาเวลาไปทำอย่างอื่นนั่นเอง
*ปัญหาอื่นๆก็มีแต่ไม่กล่าวถึงในที่นี้ ซึ่งเป็นปัญหาที่ยาก และตรวจคำตอบก็ยาก
เช่น การหาตาเดินเดินหมากรุกที่ดีที่สุดว่าต้องเป็นอย่างไร
ต่อให้บอกคำตอบที่ถูกต้องมาก็ยากต่อการตรวจสอบความถูกต้องว่ามันดีที่สุดแล้วจริงหรือ
- 12
โฆษณา
- ดาวน์โหลดแอปพลิเคชัน
- © 2025 Blockdit
