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

รุ่นแก้ไขปัจจุบันเมื่อ 19:34, 28 พฤศจิกายน 2549

เนื้อหา

1 เกริ่น
2 Levin's search
3 บทสรุป
4 ปัญหาคิดเล่น

เกริ่น

"Only math nerds would call $2^{500}$ finite"

Leonid Levin

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

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

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

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

Levin's search

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

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

$P_{1},P_{2},\ldots ,$

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

สมมติว่าโปรแกรมแยกตัวประกอบที่ดีที่สุดคือ $P_{30}$ สังเกตุว่าทุกๆ $2^{30}$ รอบการทำงาน โปรแกรม $P_{3}0$ จะทำงานไป 1 ขั้น ดังนั้น

time(LevinSearch(x))\leq 2^{30}time(P_{30}(x))+poly(|x|)

และ $2^{30}$ เป็นค่าคงที่ๆไม่ขึ้นกับขนาดของอินพุต

หลักการทำงานของวิธีนี้ก็คือการที่ลองรันโปรแกรมที่เป็นไปได้ทั้งหมดทีละโปรแกรม โดยที่แต่ละโปรแกรมจะไม่รันจนจบ แต่จะรันเพียงแค่ $1/2^{i}$ ของคาบเวลา (ขอให้มองข้ามเรื่องของที่เวลาหนึ่งหน่วยไม่สามารถแบ่งย่อยได้ไปก่อน เพื่อความสะดวกในการเข้าใจการทำงานของวิธีนี้) เนื่องจากว่าบางโปรแกรมอาจจะรันไม่รู้จบ วิธีนี้จึงเลี่ยงความเสี่ยงของการรันโปรแกรมที่ไม่รู้ว่าจะจบหรือเปล่าได้ ส่วนเหตุผลว่าทำไมถึงต้องรันโปรแกรมที่ i เป็นเวลา $1/2^{i}$ ขอให้ผู้อ่านลองไปคิดดู (ลองคิดว่าหากรันแต่ละโปรแกรมทีละขั้น วิธีนี้จะใช้ได้หรือไม่)

สังเกตว่าค่าคงที่ดังกล่าวจะขึ้นกับลำดับของโปรแกรมในลิสต์ที่เป็นไปได้ทั้งหมด หากโปรแกรมที่ดีที่สุดอยู่ในลำดับที่ k ของลิสต์ เวลาการทำงานของวิธีนี้จะไม่เกิน $2^{k}$ เท่าของเวลาการทำงานที่ดีที่สุด ลองมานึกให้ดีกว่านั้น ถ้าลำดับของโปรแกรมที่อยู่ในลิสต์เป็นการเรียงลำดับตามขนาดของโปรแกรม สมมติว่าโปรแกรมที่แก้ปัญหาการแยกตัวประกอบมีขนาดเป็น n ดังนั้นโปรแกรมนี้จะอยู่ในลำดับที่ $2^{n}$ ของลิสต์นี้ และค่าคงที่ของเลวินจะมีค่าเป็น $2^{2^{n}}$

บทสรุป

วิธีของเลวินทำให้เราได้วิธีการหาคำตอบของปัญหาที่ตรวจคำตอบได้ง่าย (ปัญหาเอ็นพี) ทั้งหมด หากแต่ว่าค่าคงที่ๆได้จะเป็นค่าที่มากมายอย่างมหาศาลที่สุด มากกว่าจำนวนอะตอมทั้งหมดในจักรวาล มากกว่าค่าใดๆที่คนจินตนาการได้ แต่เป็นค่าคงที่

ปัญหาคิดเล่น

พิสูจน์ข้อความต่อไปนี้ "ถ้า P=NP แล้ว อัลกอริทึมของเลวินเป็นอัลกอริทึมที่ทำงานในเวลาพหุนามกับขนาดอินพุตสำหรับทุกๆปัญหาเอ็นพี, ใช้เวลาในการทำงานเทียบกับวิธีการแก้ปัญหาที่ดีที่สุดแล้ว เป็นค่าคงที่, และสามารถหาคำตอบของปัญหาเอ็นพีได้ทุกปัญหา"
เลโอนิด เลวิน คิดวิธีการบ้าๆแบบนี้ขึ้นมาได้อย่างไร?

@@ แถว 1: / แถว 1: @@
 == เกริ่น ==
 ''"Only math nerds would call <math>2^{500}</math> finite"
 Leonid Levin
 ''
@@ แถว 11: / แถว 12: @@
 วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ
-ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที
+ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถแยกตัวประกอบได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที
+กลุ่มวิจัย RSA ได้ตั้งรางวัลไว้สำหรับผู้ที่สามารถใช้คอมพิวเตอร์แยกตัวประกอบจำนวนขนาดใหญ่ได้ในเวลาสั้นๆ [http://www.rsasecurity.com/rsalabs/node.asp?id=2092] (โดยปกติแล้วปัญหาการแยกตัวประกอบจำนวนใหญ่ๆเชื่อว่า ต่อให้รันโปรแกรมไปจนโปรแกรมเมอร์แก่ตาย คอมพิวเตอร์ก็ยังแยกตัวประกอบไม่เสร็จ)
 == Levin's search ==
+เลวินมีวิธีที่สามารถแยกตัวประกอบจำนวนได้ โดยใช้เวลาในการทำงานไม่เกินค่าคงที่ค่าหนึ่งคูณกับเวลาการทำงานของวิธีการแยกตัวประกอบที่ดีที่สุด สมมติว่าการแยกตัวประกอบที่ดีที่สุดใช้เวลา 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> สังเกตุว่าทุกๆ <math> 2^{30} </math> รอบการทำงาน โปรแกรม <math>P_30</math> จะทำงานไป 1 ขั้น ดังนั้น
+:: <math>time(LevinSearch(x)) \le 2^{30} time(P_{30}(x)) + poly(|x|) </math>
+และ<math> 2^{30}</math> เป็นค่าคงที่ๆไม่ขึ้นกับขนาดของอินพุต
+หลักการทำงานของวิธีนี้ก็คือการที่ลองรันโปรแกรมที่เป็นไปได้ทั้งหมดทีละโปรแกรม โดยที่แต่ละโปรแกรมจะไม่รันจนจบ แต่จะรันเพียงแค่ <math>1/2^i</math> ของคาบเวลา (ขอให้มองข้ามเรื่องของที่เวลาหนึ่งหน่วยไม่สามารถแบ่งย่อยได้ไปก่อน เพื่อความสะดวกในการเข้าใจการทำงานของวิธีนี้) เนื่องจากว่าบางโปรแกรมอาจจะรันไม่รู้จบ วิธีนี้จึงเลี่ยงความเสี่ยงของการรันโปรแกรมที่ไม่รู้ว่าจะจบหรือเปล่าได้ ส่วนเหตุผลว่าทำไมถึงต้องรันโปรแกรมที่ i เป็นเวลา <math> 1/2^i </math> ขอให้ผู้อ่านลองไปคิดดู (ลองคิดว่าหากรันแต่ละโปรแกรมทีละขั้น วิธีนี้จะใช้ได้หรือไม่)
+สังเกตว่าค่าคงที่ดังกล่าวจะขึ้นกับลำดับของโปรแกรมในลิสต์ที่เป็นไปได้ทั้งหมด หากโปรแกรมที่ดีที่สุดอยู่ในลำดับที่ k ของลิสต์ เวลาการทำงานของวิธีนี้จะไม่เกิน<math> 2^k</math> เท่าของเวลาการทำงานที่ดีที่สุด ลองมานึกให้ดีกว่านั้น ถ้าลำดับของโปรแกรมที่อยู่ในลิสต์เป็นการเรียงลำดับตามขนาดของโปรแกรม สมมติว่าโปรแกรมที่แก้ปัญหาการแยกตัวประกอบมีขนาดเป็น n ดังนั้นโปรแกรมนี้จะอยู่ในลำดับที่ <math>2^n</math> ของลิสต์นี้  และค่าคงที่ของเลวินจะมีค่าเป็น <math>2^{2^n}</math>
 == บทสรุป ==
+วิธีของเลวินทำให้เราได้วิธีการหาคำตอบของปัญหาที่ตรวจคำตอบได้ง่าย (ปัญหาเอ็นพี) ทั้งหมด หากแต่ว่าค่าคงที่ๆได้จะเป็นค่าที่มากมายอย่างมหาศาลที่สุด มากกว่าจำนวนอะตอมทั้งหมดในจักรวาล มากกว่าค่าใดๆที่คนจินตนาการได้ แต่เป็น'''ค่าคงที่'''
+== ปัญหาคิดเล่น ==
+# พิสูจน์ข้อความต่อไปนี้ "ถ้า P=NP แล้ว อัลกอริทึมของเลวินเป็นอัลกอริทึมที่ทำงานในเวลาพหุนามกับขนาดอินพุตสำหรับทุกๆปัญหาเอ็นพี, ใช้เวลาในการทำงานเทียบกับวิธีการแก้ปัญหาที่ดีที่สุดแล้ว เป็นค่าคงที่, และสามารถหาคำตอบของปัญหาเอ็นพีได้ทุกปัญหา"
+# เลโอนิด เลวิน คิดวิธีการบ้าๆแบบนี้ขึ้นมาได้อย่างไร?

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

รุ่นแก้ไขปัจจุบันเมื่อ 19:34, 28 พฤศจิกายน 2549

เนื้อหา

เกริ่น

Levin's search

บทสรุป

ปัญหาคิดเล่น

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ