ผลต่างระหว่างรุ่นของ "ตอนที่ 1: Levin's Search กับการแยกตัวประกอบของจำนวน"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 19: แถว 19:
 
== Levin's search ==  
 
== Levin's search ==  
  
เลวินมีวิธีที่สามารถแยกตัวประกอบจำนวนได้ โดยใช้เวลาในการทำงานไม่เกินค่าคงที่ค่าหนึ่งคูณกับเวลาการทำงานของวิธีการแยกตัวประกอบที่ดีที่สุด สมมติว่าการแยกตัวประกอบที่ดีที่สุดใช้เวลา 10 ปี วิธีของเลวินก็จะใช้เวลาไม่เกินค่าคงที่คูณกับสิบปีนั้น นอกเหนือไปกว่านั้นวิธีของเลวินสามารถใช้ในการหาคำตอบของ ''ปัญหาใดก็ได้'' ที่เราสามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ และใช้เวลาในการทำงานเป็นค่าคงที่คูณกับเวลาที่ใช้ของวิธีที่ดีที่สุดเช่นกัน คำว่าค่าคงที่นี้เป็นค่าคงที่ๆขึ้นกับปัญหา แต่ไม่ขึ้นกับขนาดของข้อมูลป้อนเข้า เช่น ปัญหาการแยกตัวประกอบ ค่าคงที่ดังกล่าวอาจจะเป็น 20 แต่ปัญหาอย่างอื่นก็อาจจะมีค่าคงที่ที่แตกต่างกันไป  
+
เลวินมีวิธีที่สามารถแยกตัวประกอบจำนวนได้ โดยใช้เวลาในการทำงานไม่เกินค่าคงที่ค่าหนึ่งคูณกับเวลาการทำงานของวิธีการแยกตัวประกอบที่ดีที่สุด สมมติว่าการแยกตัวประกอบที่ดีที่สุดใช้เวลา 10 ปี วิธีของเลวินก็จะใช้เวลาไม่เกินค่าคงที่คูณกับสิบปีนั้น นอกเหนือไปกว่านั้นวิธีของเลวินสามารถใช้ในการหาคำตอบของ ''ปัญหาใดก็ได้'' ที่เราสามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ และใช้เวลาในการทำงานเป็นค่าคงที่คูณกับเวลาที่ใช้ของวิธีที่ดีที่สุดเช่นกัน คำว่าค่าคงที่นี้เป็นค่าคงที่ๆขึ้นกับปัญหา แต่ไม่ขึ้นกับขนาดของข้อมูลป้อนเข้า เช่น ปัญหาการแยกตัวประกอบ ค่าคงที่ดังกล่าวอาจจะเป็น 20 แต่ปัญหาอย่างอื่นก็อาจจะมีค่าคงที่ที่แตกต่างกันไป ลองมาดูกันว่าวิธีดังกล่าวเป็นอย่างไร
  
+
ก่อนอื่นเลวินมองลิสต์ของ โปรแกรมคอมพิวเตอร์ ที่เป็นไปได้ทั้งหมดในโลก ผู้อ่านอาจจะนึกภาพว่าเป็นโปรแกรมภาษาจาวา
  
 +
<math> P_1, P_2, \ldots, </math>
 +
 +
    ''Levin_Search(x)''
 +
    ที่เวลาใดๆ
 +
      รันโปรแกรม <math> P_i(x) </math> เป็นเวลา <math> 1/2^i </math> 
 +
        ถ้าได้ผลลัพธ์ y และ z จาก <math> P_i(x) </math> ให้ทดสอบว่า x= yz หรือไม่
 +
            ถ้าใช่ จบการทำงาน และตอบ y,z
 +
 +
สมมติว่าโปรแกรมแยกตัวประกอบที่ดีที่สุดคือ <math> P_30</math>
  
 
== บทสรุป ==
 
== บทสรุป ==

รุ่นแก้ไขเมื่อ 07:11, 21 พฤศจิกายน 2549

เกริ่น

"Only math nerds would call finite" Leonid Levin

Levin.jpg

ปัญหาการแยกตัวประกอบจำนวนก็คือปัญหาที่เรามีจำนวนจำนวนหนึ่งที่เป็นจำนวนประกอบ n เราจะสามารถหาวิธีการที่มีประสิทธิภาพที่สุดในการแยกตัวประกอบของจำนวนนั้นได้อย่างไร หากลองมองกลับไปวิธีที่ใช้สอนเด็กประถม เราอาจจะทำได้ดังนี้ ลองหารจำนวนตั้งแต่ 1, 2, 3 จนกระทั่งพบจำนวนแรกที่หารจำนวนนั้นลงตัว เท่านี้ก็แยกตัวประกอบสำเร็จ

วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ

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

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


Levin's search

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

ก่อนอื่นเลวินมองลิสต์ของ โปรแกรมคอมพิวเตอร์ ที่เป็นไปได้ทั้งหมดในโลก ผู้อ่านอาจจะนึกภาพว่าเป็นโปรแกรมภาษาจาวา

    Levin_Search(x) 
    ที่เวลาใดๆ
      รันโปรแกรม  เป็นเวลา    
        ถ้าได้ผลลัพธ์ y และ z จาก  ให้ทดสอบว่า x= yz หรือไม่ 
            ถ้าใช่ จบการทำงาน และตอบ y,z 

สมมติว่าโปรแกรมแยกตัวประกอบที่ดีที่สุดคือ

บทสรุป