complexity_theory Archive

นักวิจัยที่อิตาลีพิสูจน์ว่าเกมแพ็ก-แมน (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

Continue Reading...