ตอนที่ 1: Levin's Search กับการแยกตัวประกอบของจำนวน - ประวัติรุ่นแก้ไข

Parinya: /* ปัญหาคิดเล่น */

2006-11-28T19:34:33Z

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

Parinya: /* ปัญหาคิดเล่น */

2006-11-28T19:31:46Z

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

Parinya: /* Levin's search */

2006-11-28T09:30:21Z

Levin's search

Parinya: /* ปัญหาคิดเล่น */

2006-11-28T09:28:07Z

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

Parinya: /* บทสรุป */

2006-11-28T09:26:15Z

บทสรุป

128.135.226.62: /* Levin's search */

2006-11-23T04:02:22Z

Levin's search

128.135.226.62: /* เกริ่น */

2006-11-21T08:45:48Z

เกริ่น

Parinya: /* Levin's search */

2006-11-21T07:29:23Z

Levin's search

Parinya: /* Levin's search */

2006-11-21T07:23:57Z

Levin's search

Parinya เมื่อ 07:17, 21 พฤศจิกายน 2549

2006-11-21T07:17:32Z

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

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

@@ แถว 32: / แถว 32: @@
 สมมติว่าโปรแกรมแยกตัวประกอบที่ดีที่สุดคือ <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>time(LevinSearch(x)) \le 2^{30} time(P_{30}(x)) + poly(|x|) </math>
 และ<math> 2^{30}</math> เป็นค่าคงที่ๆไม่ขึ้นกับขนาดของอินพุต

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:28, 28 พฤศจิกายน 2549
แถว 47:		แถว 47:

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:26, 28 พฤศจิกายน 2549
แถว 43:		แถว 43:

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

@@ แถว 12: / แถว 12: @@
 วิธีนี้อาจจะใช้ได้ผลดีหากตัวเลขมีค่าไม่มากนัก แต่ในแง่ของนักวิทยาการคอมพิวเตอร์แล้ว วิธีนี้ถือว่าสิ้นเปลืองเวลาและพลังงานชิวิตของคอมพิวเตอร์เป็นอย่างมาก ในการคิดความเร็วในการคำนวณของคอมพิวเตอร์นั้น เราจะคิดความเร็วเทียบกับขนาดของข้อมูลที่ป้อนเข้า หาก n มีค่าเป็น 3,000,013 ขนาดของข้อมูลที่ป้อนเข้าก็คือ 7 หลักเท่านั้น แต่วิธีการแยกตัวประกอบดังกล่าวอาจใช้เวลาการทำงานนับหมื่นรอบ เพื่อหาจำนวนดังกล่าว ดังนั้นแล้ววิธีนี้จึงถือว่าไม่มีประสิทธิภาพ
-ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถถอดรหัสได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที
+ในด้านวิทยาการคอมพิวเตอร์นั้น ปัญหาการแยกตัวประกอบถือว่าเป็นปัญหาที่ยากมาก การเข้ารหัสเกือบทั้งหมดในปัจจุบันถูกสร้างขึ้นมาโดยสมมติฐานที่ว่า ผู้ที่ต้องการขโมยข้อมูลไม่สามารถแยกตัวประกอบได้ เพราะฉะนั้น หากมีผู้ใดค้นพบวิธีการแยกตัวประกอบอย่างมีประสิทธิภาพ ระบบความปลอดภัยในคอมพิวเตอร์เกือบทั้งหมดก็จะกลายเป็นไม่ปลอดภัยทันที
 กลุ่มวิจัย RSA ได้ตั้งรางวัลไว้สำหรับผู้ที่สามารถใช้คอมพิวเตอร์แยกตัวประกอบจำนวนขนาดใหญ่ได้ในเวลาสั้นๆ [http://www.rsasecurity.com/rsalabs/node.asp?id=2092] (โดยปกติแล้วปัญหาการแยกตัวประกอบจำนวนใหญ่ๆเชื่อว่า ต่อให้รันโปรแกรมไปจนโปรแกรมเมอร์แก่ตาย คอมพิวเตอร์ก็ยังแยกตัวประกอบไม่เสร็จ)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:29, 21 พฤศจิกายน 2549
แถว 35:		แถว 35:

	และ<math> 2^{30}</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>		สังเกตว่าค่าคงที่ดังกล่าวจะขึ้นกับลำดับของโปรแกรมในลิสต์ที่เป็นไปได้ทั้งหมด หากโปรแกรมที่ดีที่สุดอยู่ในลำดับที่ k ของลิสต์ เวลาการทำงานของวิธีนี้จะไม่เกิน<math> 2^k</math> เท่าของเวลาการทำงานที่ดีที่สุด ลองมานึกให้ดีกว่านั้น ถ้าลำดับของโปรแกรมที่อยู่ในลิสต์เป็นการเรียงลำดับตามขนาดของโปรแกรม สมมติว่าโปรแกรมที่แก้ปัญหาการแยกตัวประกอบมีขนาดเป็น n ดังนั้นโปรแกรมนี้จะอยู่ในลำดับที่ <math>2^n</math> ของลิสต์นี้ และค่าคงที่ของเลวินจะมีค่าเป็น <math>2^{2^n}</math>

@@ แถว 35: / แถว 35: @@
 และ<math> 2^{30}</math> เป็นค่าคงที่ๆไม่ขึ้นกับขนาดของอินพุต
 == บทสรุป ==
 วิธีของเลวินทำให้เราได้วิธีการหาคำตอบของปัญหาที่ตรวจคำตอบได้ง่าย (ปัญหาเอ็นพี) ทั้งหมด หากแต่ว่าค่าคงที่ๆได้จะเป็นค่าที่มากมายอย่างมหาศาลที่สุด มากกว่าจำนวนอะตอมทั้งหมดในจักรวาล มากกว่าค่าใดๆที่คนจินตนาการได้ แต่เป็น'''ค่าคงที่'''

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:17, 21 พฤศจิกายน 2549
แถว 37:		แถว 37:

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