ACM มอบรางวัล Turing Award พร้อมเงินรางวัลล้านดอลลาร์ให้กับ Avi Wigderson จากการที่เขาเป็นนักวิจัยสำคัญในวงการ theory of computation โดยเฉพาะความเข้าใจความสำคัญของการสุ่มค่าในอัลกอริทึม

โดยทั่วไปแล้วอัลกอรึทึมที่เราใช้งานและคอมพิวเตอร์คำนวณให้จะเป็นระบบ deterministic หมายความว่าข้อมูลเข้าจะกำหนดผลลัพธ์และระยะเวลาที่ใช้คำนวณเสมอ ทำให้พฤติกรรมของอัลกอรึทึมคาดเดาได้ แต่อัลกอรึทึมหลายตัวอาศัยการสุ่มค่าเพื่อเพิ่มประสิทธิภาพ (มั่วแล้วเร็วขึ้น) โดยปัญหาหลายอย่างไม่มีทางคำนวณอย่างมีประสิทธิภาพเลย หากไม่อาศัยการสุ่มค่า วงการวิจัย theory of computation พยายามทำความเข้าใจความสำคัญของการสุ่มค่าเช่นนี้ เช่น จำเป็นต้องมีการสุ่มที่ดีหรือไม่ หรือสามารถถอดการสุ่มค่าทิ้งไปเลยได้หรือไม่

งานวิจัยของ Wigderson สาธิตถึงการใช้กระบวนการสุ่มค่าเทียม (pseudorandom generator - อ่านเพิ่มเติมบทความเก่า) ก็ยังใช้งานเหมือนการสุ่มค่าได้ครอบคลุมหลายกรณี

ที่มา - ACM