อธิบายมาเสียยืดยาว มาตกม้าตาย ตอนจบซะนี่เรา
อย่างที่ คุณ warut บอกครับ quantum computer ทำให้บางปัญหาในกลุ่ม NP เท่านั้น ที่สามารถคำนวณเสร็จ ด้วยเวลาที่มนุษย์คอยได้ หรือพูดแบบวิชาการหน่อยก็คือ เวลาจำกัดอยู่ใน polynomial time
ปัญหาการหาทางเดินใน hamiltonian graph เป็นส่วนหนึ่งของปัญหา NP หรือจะให้ระบุให้ชัดกว่านี้ ก็คือเป็นแบบ NP-complete
ส่วนประเด็นที่ว่า quantum computer ยังไม่สามารถทำให้ NP-complete คำนวณใน polynomial time อันนี้ผมก็ไม่แน่ใจครับ เท่าที่เห็นข่าวเกี่ยวกับ Quantum computer ตอนนี้ ส่วนใหญ่จะเกี่ยวกับปัญหาประมาณว่า quantum bit ไม่เสถียรเพียงพอ เลยต้องแก้ไข พัฒนากันต่อไป
เอาเป็นว่ายืนยัน ตามที่คุณ warut บอกไว้ก่อนแล้วกันครับว่า ยัง solve NP-complete ไม่ได้ (เพราะถ้าได้ น่าจะเป็นข่าวใหญ่โตในวงการ quantum computer ไปนานแล้ว)
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว
|