ปัญหาความซับซ้อนในการคำนวณ

คอมพิวเตอร์ถึงจะทำงานได้เร็วแต่ก็มีข้อจำกัด หากมันเจอกับโจทย์ที่เป็นปัญหาซับซ้อนในการคำนวณ ซึ่งเท่าที่ผมเคยเผชิญมันมีอยู่ 2 แบบใหญ่ ๆ (และยังมีแบบอื่นอีก) คือ แบบที่ต้องคำนวณด้วยเวลา C ยกกำลัง N กับ แบบที่ต้องคำนวณด้วยเวลา 2 ยกกำลัง N แล้วจึงลบ 1

โดย N คือจำนวนของขนาดปัญหาที่เป็นไปได้

อย่างแบบแรก ยกตัวอย่างให้เห็นง่าย ๆ ก็คือ ถ้าเรามีเสื้อ 2 ตัว กางเกง 2 ตัว รองเท้า 2 คู่ เราจะเลือกใส่ เสื้อ กางเกง และ รองเท้า ยังไงให้หล่อที่สุด ซึ่งจากโจทย์ C ก็คือ 2 เพราะบังเอิญว่าแต่ล่ะตัวแปรมี 2 กรณีให้เลือก ในขณะที่ N คือ 3 เพราะขนาดปัญหา คือ 3 ตัวแปร คือ 1) เสื้อ 2) กางเกง 3) รองเท้า ดังนั้น ถ้าจะหาคำตอบที่ดีที่สุด เราก็ต้องลอง เสื้อ กางเกง รองเท้า ให้มันหมดเลย ซึ่งต้องใช้เวลาเท่ากับ C ยกกำลัง N หรือ 2 ยกกำลัง 3 ซึ่งก็คือ {1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {2, 1, 1}, {2, 1, 2}, {2, 2, 1} และ {2, 2, 2} หรือก็คือใช้เวลาไป 8 รอบ

ส่วนแบบสอง ยกตัวอย่างให้เห็นง่าย ๆ ก็คือ ถ้าในร้านค้ามีสินค้าเพียง 3 ชิ้นที่แตกต่างกัน แล้วเรามีเงินอยู่แค่ 100 บาท เราจะซื้อสินค้าได้กี่่ชิ้น ซึ่งจากโจทย์ N ก็คือ 3 เพราะขนาดปัญหา คือ 3 ดังนั้น ถ้าจะหาคำตอบที่ดีที่สุด เราก็ต้องเอาราคาสินค้ามาเทียบกันให้หมดเลย เพื่อดูว่ารวมเงินแล้วจะซื้อชิ้นไหนได้บ้างโดยใช้เงินไม่เกิน 100 บาท ซึ่งต้องใช้เวลาคำนวณเท่ากับ 2 ยกกำลัง 3 แล้วจึงลบ 1 ซึ่งน้อย ๆ แบบนี้ยังพอยกตัวอย่างให้ดูได้ ก็ประมาณนี้คือ {1}, {2}, {3}, {1,2}, {1,3}, {2,3} และ {1,2,3} หรือก็คือใช้เวลาไป 7 รอบ

ทุกวันนี้ไม่มีใครสนใจใช้วิธีการหาคำตอบทั้งหมดเพื่อเลือกคำตอบที่ดีที่สุดบนดิจิทัลคอมพิวเตอร์กันแล้ว เขาหันไปใช้วิธีการตัดเล็มตัวเลือกที่อ่อนด๋อย เพื่อจะได้เหลือเฉพาะตัวเลือกที่ดีที่สุด หรือไม่เขาก็ไปใช้วิธีการอนุมานอย่างมีเหตุผลเพื่อเลือกคำตอบที่น่าจะดีที่สุดแทน

ต่อให้มีควอนตัมคอมพิวเตอร์ให้ใช้กัน ผมก็ยังเชื่อว่าปัญหาความซับซ้อนในการคำนวณจะยังคงถูกต่อยอดคิดค้นให้มาแก้กันต่อไป จนกว่าจะมีใครซักคนคิดค้นสมการเทพ ๆ ที่ใส่ค่าทีเดียวแล้วได้คำตอบทุกอย่าง หรือจนกว่าคอมพิวเตอร์คำนวณชั่วพริบตาขณะจิตจะถูกสร้างขึ้นนั่นแหล่ะ ปัญหานี้ถึงจะหมดไป