นักวิจัยพิสูจน์ว่าแพ็ก-แมนเป็นปัญหาแบบ NP-hard

นักวิจัยที่อิตาลีพิสูจน์ว่าเกมแพ็ก-แมน (Pac-Man) ที่เราเคยเล่นกันนั้นแท้จริงแล้วเป็นปัญหาชนิด NP-hard

Giovanni Viglietta จากมหาวิทยาลัยแห่งปิซาทำวิจัยจำแนกเกมคลาสสิก 13 เกมเป็นปัญหาชนิดต่าง ๆ เช่น แพ็ก-แมนหรือสตาร์คราฟต์ (StarCraft) เป็น NP-hard ส่วนปรินซ์ออฟเปอร์เชีย (Prince of Persia) นั้นเป็น PSPACE-complete ในขณะที่ดูม (Doom) เป็นแบบ PSPACE-hard

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

ส่วนคนที่ไม่คุ้นกับการวัดระดับความยากนั้นอาจเคยได้ยินปัญหาอย่างปัญหาการเดินทางของพนักงานขาย (travelling salesman problem หรือ TSP) ซึ่งถูกจัดว่าเป็นปัญหาแบบ NP-hard เช่นกัน

ใครสนใจลองตามอ่านเปเปอร์ต้นฉบับด้านล่างครับ

อ้างอิง

• http://arxiv.org/abs/1201.4995
• http://www.extremetech.com/gaming/115677-pac-man-is-np-hard-same-as-travelling-salesman-problem
• http://en.wikipedia.org/wiki/Computational_complexity_theory