ปัญหารางวัลมิลเลนเนียม

ปัญหารางวัลมิลเลนเนียม (อังกฤษ: Millennium Prize Problems) เป็นปัญหาที่อยู่บนพื้นฐานของคณิตศาสตร์ 7 ข้อ ซึ่งเสนอในปีค.ศ. 2000 โดยสถาบันคณิตศาสตร์เคลย์ จากการรวบรวมปัญหาสำคัญในวงการวิทยาการคอมพิวเตอร์ ฟิสิกส์ และคณิตศาสตร์ ซึ่งยังพิสูจน์ไม่สำเร็จในขณะนั้น ให้เป็นปัญหาแห่งคริสต์ศตวรรษที่ 21 โดยสถาบันคณิตศาสตร์เคลย์ได้ประกาศมอบเงินรางวัลหนึ่งล้านดอลลาร์สหรัฐให้กับผู้ที่สามารถพิสูจน์ปัญหาข้อใดข้อหนึ่งได้สำเร็จ ในปี ค.ศ. 2006 สถาบันคณิตศาสตร์เคลย์ได้มอบรางวัลหนึ่งล้านดอลลาร์สหรัฐ ให้กับกริกอรี เพเรลมาน ผู้พิสูจน์ข้อความคาดการณ์ของปวงกาเร หนึ่งในปัญหารางวัลมิลเลนเนียมได้สำเร็จ และยังเป็นปัญหารางวัลมิลเลนเนียมเพียงปัญหาเดียวที่พิสูจน์สำเร็จจนถึงปัจจุบันนี้ ปัญหารางวัลมิลเลนเนียมทั้ง 7 ข้อ ได้แก่ ปัญหาพีและเอ็นพีเป็นปัญหาสำคัญทางวิทยาการคอมพิวเตอร์และทฤษฎีการคำนวณ ซึ่งศึกษาความซับซ้อนในการคำนวณ ระหว่างกลุ่มความซับซ้อนพี (P) ซึ่งเป็นกลุ่มปัญหาที่สามารถ ค้นหา (search) คำตอบได้ในเวลาพหุนาม กับกลุ่มความซับซ้อนเอ็นพี (NP) ซึ่งเป็นกลุ่มปัญหาที่สามารถ ตรวจสอบ (verify) คำตอบได้ในเวลาพหุนาม ปัญหาพีและเอ็นพีตั้งข้อสงสัยว่ากลุ่มความซับซ้อนพีและเอ็นพีเป็นกลุ่มปัญหาเดียวกันหรือไม่ ? เพราะกลุ่มความซับซ้อนพีจะเป็นเซตย่อยของกลุ่มความซับซ้อนเอ็นพีเสมอ เนื่องจากเราสามารถตรวจสอบ คำตอบด้วยการ ค้นหา คำตอบได้ แต่ในปัจจุบันยังพิสูจน์ไม่ได้ว่ากลุ่มความซับซ้อนเอ็นพีจะเป็นเซตย่อยของกลุ่มความซับซ้อนพีหรือไม่? เนื่องจากมีกลุ่มปัญหาเอ็นพีบริบูรณ์ (NP-Complete) ซึ่งสามารถ ตรวจสอบ คำตอบได้ในเวลาพหุนาม แต่ยังไม่พบ ขั้นตอนวิธี ค้นหา คำตอบด้วยความเร็วระดับเวลาพหุนาม เนื่องจากกลุ่มปัญหาเอ็นพีบริบูรณ์เป็นกลุ่มปัญหาที่ลดรูปซึ่งกันและกัน และลดรูปกับกลุ่มปัญหาเอ็นพีทั้งหมด ดังนั้นหากค้นพบขั้นตอนวิธี ค้นหา คำตอบของปัญหาเอ็นพีบริบูรณ์ปัญหาใดปัญหาหนึ่งเป็นเวลาพหุนาม กลุ่มความซับซ้อนพีจะเป็นกลุ่มปัญหาเดียวกับกลุ่มความซับซ้อนเอ็นพี แต่หากมีบทพิสูจน์ว่าไม่มีขั้นตอนวิธีใดสามารถ ค้นหา คำตอบของปัญหาเอ็นพีบริบูรณ์เป็นเวลาพหุนาม กลุ่มความซับซ้อนพีจะไม่ใช่กลุ่มปัญหาเดียวกับกลุ่มความซับซ้อนเอ็นพี หากกลุ่มความซับซ้อนพีเท่ากับกลุ่มความซับซ้อนเอ็นพี ปัญหาใดที่ ตรวจสอบ คำตอบได้ในเวลาพหุนาม จะสามารถ ค้นหา คำตอบได้ในเวลาพหุนามไปด้วย ทำให้การ ค้นหา ซึ่งเป็นปัญหาสำคัญทางวิทยาการคอมพิวเตอร์ สามารถทำได้รวดเร็วมากขึ้น และถึงแม้พิสูจน์ได้ว่ากลุ่มความซับซ้อนพีไม่เท่ากับกลุ่มความซับซ้อนเอ็นพี นักคณิตศาสตร์ และวิทยาการคอมพิวเตอร์ก็จะเข้าใจรายละเอียดของการ ตรวจสอบ และการ ค้นหา มากขึ้น และทำให้เข้าใจปัญหาทางคณิตศาสตร์ ชีววิทยา ปรัชญา และปัญหาวิทยาการรหัสลับได้อย่างลึกซึ้งขึ้น ปัจจุบัน นักคณิตศาสตร์และวิทยาการคอมพิวเตอร์ส่วนใหญ่เชื่อว่า P ≠ NP ปัญหานี้ถูกตั้งข้อสงสัย และเสนออย่างเป็นทางการโดย สตีเฟน คุก ข้อความคาดการณ์ของปวงกาเรเป็นปัญหาสำคัญทางทอพอโลยี ซึ่งศึกษาสมานสัณฐาน (Homeomorphism) กล่าวคือ ความสามารถในการยืดหดของพื้นผิว (Manifold) ต่าง ๆ ระหว่างคุณสมบัติที่ห่วง (Loop) บนพื้นผิวนั้นสามารถหดลงจนกลายเป็นจุด (Simply connected) กับความสามารถในการยืดหดพื้นผิวให้กลายเป็นทรงกลมได้ ในโลก 3 มิติ อองรี ปวงกาเร พิสูจน์ได้ว่า พื้นผิวสอง มิติปิด (Closed) ที่ห่วงบนพื้นผิวนั้นสามารถหดลงจนกลายเป็นจุดได้ จะยืดหดพื้นผิวเป็นผิวทรงกลมได้เสมอ ข้อคาดการณ์ของปวงกาเรตั้งข้อสงสัยว่าในโลก 4 มิติ พื้นผิว 3 มิติใด ๆ ที่ห่วงบนพื้นผิวสามารถหดลงจนกลายเป็นจุด จะยืดหดพื้นผิวเป็นทรงกลมผิว 3 มิติได้หรือไม่ ? ทั้งนี้พื้นผิว 4 มิติได้รับการพิสูจน์ว่าจริงในปี ค.ศ. 1961 โดย Stephen Smale และพื้นผิวที่มากกว่า 4 มิติขึ้นไปได้รับการพิสูจน์ว่าจริง Michael Freedman ในปีค.ศ. 1982 แต่พื้นผิว 3 มิติ กลับเป็นปัญหาเดียวที่ยังพิสูจน์ไม่ได้จนถึงค.ศ. 2000 จนในที่สุด ในปีค.ศ