Internet & Web Application

Computer Science Problems

อ้างอิงจาก http://kitty.in.th/index.php?room=article&id=80

โดยทั่วไปเวลาในการประมวลผลจะขึ้นกับความซับซ้อนของปัญหา ในคอมพิวเตอร์เราแบ่งความซับซ้อนของปัญหาออกเป็น 4 classes ครับ คือ P-problems, NP-Problems, NP-complete problems และ Exponential problems:

  1. P-problems ก็คือปัญหาที่สามารถแก้ได้ในขอบเขตของ polynomial time/space – จำนวนครั้งในการประมวลผลอยู่ในขอบเขตของ nc เมื่อ n เป็นขนาดของปัญหาและ c เป็นค่าคงที่ที่หาได้แน่นอน ปัญหาระดับ P-problem ถือว่าเป็นแก้ได้ง่ายที่สุด และใช้ทรัพยากรน้อยที่สุด
  2. NP-problems เป็น nondeterministic polynomial time อธิบายง่ายๆ หน่อยก็คือแต่ละ n ต้องเดาว่าคำตอบคืออะไรและการจะหาว่าคำตอบนั้นถูกหรือไม่สามารถทำได้ในขอบ เขตของ polynomial time/space ไม่ว่าคำตอบนั้นจะถูกหรือผิด มีปัญหาหลายๆอันที่นักคณิตศาสตร์เคยคิดว่าเป็น NP-problem แต่จริงๆ แล้วไม่ใช่ การที่มีคนพิสูจน์ได้ว่าปัญหาที่เป็น NP-problem หลายๆ ปัญหาลดลงมาเหลือ P-problem ได้ ทำให้มีความหวังว่าปัญหาทั้งหมดไม่ว่าจะซับซ้อนเพียงไร ก็อาจจะหาคำตอบได้ภายในขอบเขตของ polynomial time/space
  3. NP-complete problems แบ่งเป็นสองกลุ่มย่อยคือ
    NP-Hard problem: เป็นปัญหาที่สามารถเอา algorithm ในการแก้ปัญหามาแปลงเพื่อแก้ปัญหา NP-problem อื่นๆ ได้ หรือในทางกลับกันคือ NP-problem ทุกอันสามารถแปลงเป็น NP-Hard ได้…
    NP-complete: คือปัญหาที่เป็นทั้ง NP-problem และ NP-Hard problem (เริ่มงงแล้ว…หึๆๆ) ตัวอย่างเช่น Traveling Salesman Problem (TSP) สิ่งที่น่าสนใจของ NP-complete คือ algorithm สำหรับแก้ปัญหาอย่างนึงสามารถแปลงไปแก้ปัญหา NP-complete อื่นๆ ได้..ดังนั้นเมื่อไหร่ที่ NP-complete มี algorithm ที่ลดรูปเหลือ P-problem ได้ก็จะหมายความว่า NP-complete อื่นๆ จะถูกลดลงมาเหลือแค่ P-problem ซึ่งเป็น class ที่ใช้ space/time น้อยที่สุด…มีนักคณิตศาสตร์จำนวนมากพยายามค้นหา algorithm ลักษณะนี้ จนถึงทุกวันนี้ยังไม่มีใครพบแม้แต่ algorithm เดียว.. แต่ก็ไม่สามารถพิสูจน์ว่ามันไม่มีอยู่จริง
  4. Exponential problem คือปัญหาที่แก้ได้ในขอบเขตของ exponential time/space – จำนวนครั้งในการประมวลผลอยู่ในขอบเขตของ cn ปัญหาลักษณะนี้ถือว่ามีความซับซ้อนมากที่สุด ต้องใช้ space/time สูงสุดในบรรดาปัญหาที่แก้ได้ด้วย computer .. Exponential problem ที่รู้จักกันดีก็คือ Tower of Hanoi ซึ่งมีจำนวนครั้งของการย้ายจานเป็น exponential function ของจำนวนจาน

คอมพิวเตอร์ทั่วไปเราใช้แก้ปัญหาใน class P-problem เท่านั้น หากเกินจาก P-problem แปลว่าต้องใช้เวลาหรือ resource มากเกินไป ซึ่งส่วนใหญ่ถือว่าไม่คุ้มที่จะทำ แต่ขอบเขตตรงนี้อาจจะหมดไปได้ (หรืออย่างน้อยก็ลดลงไปได้) หากเราใช้ quantum computing ..

อย่างใรก็ตาม quantum computing ไม่ได้แก้ปัญหาได้ดีกว่า computer ธรรมดาไปซะทุกอย่างหรอกครับ quantum computing ยังมีข้อจำกัดอยู่ประการหนึ่งคือการ access ข้อมูลใน qubit register จะทำได้เพียงครั้งเดียวเท่านั้น ทั้งนี้เนื่องจากการวัดค่าใดๆ กับอนุภาคที่เอามาใช้เป็น qubit register จะเป็นการทำลายสถานะของอนุภาคในขณะนั้นด้วย ข้อมูลที่ encode ไว้จึงสลายไปทันทีหลังจากถูก access ดังนั้นการจะใช้ประโยชน์จาก quantum computing จึงต้องออกแบบ algorithm ขึ้นมาเพื่อแก้ปัญหาข้อจำกัดของ qubit register และใช้ประโยชน์จาก coherent superposition กับ entanglement ให้เต็มที่ .. เราเรียก algorithm กลุ่มนี้ว่าเป็น “Quantum Algorithms” …

หลายคนมีความหวังว่า quantum algorithm บางตัวอาจจะแก้ปัญหาใน class NP-Problems ได้ แต่ปัจจุบันก็ยังไม่มีใครค้นพบ algorithm ดังกล่าว อย่างไรก็ตาม quantum algorithms ก็มีออกมาพอสมควรแล้วครับ ตัวอย่างเช่น ลอฟ โกรเวอร์ (Lov Glover) ซึ่งเป็นนักวิทยาศาสตร์ประจำบริษัท ลูเซนท
์ เทคโนโลยี เขียน quantum algorithm ในการ search ข้อมูลที่ไม่มีการเรียงลำดับได้ภายใน O(SQRT(n) ) ในขณะที่คอมพิวเตอร์ทั่วไปต้องใช้ถึง O(n/2) โดยเฉลี่ย ..

กิลส์ บราสสาร์ด (Gilles Brassard) เอา algorithm ของโกรเวอร์ มาใช้เพื่อทำการกุญแจถอดรหัสของ Data Encryption Standard (DES) .. DES ใช้กุญแจขนาด 56-bit ดังนั้นจึงมีกุญแจที่เป็นไปได้ 256 keys (ประมาณ 7 x 1016) สมมติให้คอมพิวเตอร์ทั่วไปทดสอบกุญแจได้ 1 ล้าน ตัวต่อวินาที ก็ยังต้องใช้เวลานับพันปีกว่าจะได้กุญแจที่ถูกต้อง แต่ด้วย quantum computing + Grover’s algorithm จะใช้เวลาน้อยกว่า 4 นาที .. สิ่งที่แปลงอย่างนึงของ quantum computing คือ algorithm ส่วนใหญ่มักจะเกี่ยวข้องกับ cryptography ครับ.. อย่าง ปีเตอร์ ชอร์ (Peter Shor) ก็คิด quantum algorithm สำหรับแยกตัวประกอบของเลขจำนวนเต็มขนาดใหญ่ .. ผลกระทบของ Shor’s algorithm กับ quantum computing ทำให้ cryptography ที่มีในปัจจุบันไม่ปลอดภัยเพียงพอซะแล้ว…

ต้องขอขอบคุณ Kitty.in.th ด้วยครับ

Advertisements
มาตรฐาน

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s