ขอประวัติของออยเลอร์หน่อยครับ
 

ใครมีประวัติของออยเลอร์มั่งครับ
ขอแบบละเอียดๆอ่ะครับพอจะมีไหมลองหาดุแล้วเจอแต่สั้นๆ
เอาผลงานด้วยก็ดีนะครับหาเจอแต่ทฤษฏีกราฟอย่างอื่นไม่มีบอกว่ามาจากไหนเลย

ขอบคุณครับ^^

ลองอ่านและแปลจากเว็บนี้นะครับ
The MacTutor History of Mathematics archive (Leonhard Euler)

กราฟออยเลอร์ คืออะไรอะครับ

คุณ Rover หมายถึง Eulerian cycle กับ Eulerian path หรือเปล่าครับ

ถ้า ใช่ มันก็คือ กราฟที่สามารถลากให้ผ่านทุกเส้น โดยไม่ทับเส้นเดิมที่เคยลากผ่านไปแล้ว

คล้ายๆกับ เกมที่เขาให้วาดรูปโดยไม่ยกปากกา ทำนองนั้นแหละครับ

กราฟใดที่ดีกรีของทุกจุดเป็นเลขคู่ ก็จะเป็น Eulerian cycle กล่าวคือ เป็นกราฟออยเลอร์ ประเภทที่ ลากเสร็จแล้ว วกกลับมาที่จุดเริ่มต้น

แต่ถ้ากราฟใด มีดีกรีจุด 2 จุดเท่านั้นเป็นเลขคี่ และที่เหลือเป็นเลขคู่ ก็จะเป็น Eulerian path ซึ่งก็คือ กราฟ ออยเลอร์ที่ จุดเริ่มต้นและ จุดสิ้นสุดเป็นคนละจุด

และถ้าจะถามว่า มี Eulerian cycle ที่ ดีกรีบางจุดเป็นเลขคี่ บ้างมั้ย คำตอบคือ ไม่มีครับ
ซึ่งสรุปเป็นทฤษฎีบทว่า กราฟ G มี Eulerian cycle ก็ต่อเมื่อ ดีกรีทุกจุดเป็นเลขคู่
(ในกรณีของ Eulerian path ก็เช่นเดียวกัน)

เมื่อพูดถึง กราฟออยเลอร์ ก็มักจะมีอีกคำที่คล้ายคลึงกัน คือ กราฟแฮมิลโทเนียน (Hamiltonian graph) ซึ่งเป็นประเภทที่ ลากผ่านทุกจุด โดยไม่ทับจุดเดิมที่ลากผ่านไปแล้ว

ในวิชา graph theory เราศึกษา Eulerian cycle/path กันทะลุปรุโปร่ง หมดแล้วครับ เหลือแต่เจ้า Hamiltonian graph ซึ่งยังไม่มีทฤษฎีรองรับแบบ โป้งเดียวจอด เหมือน Eulerian cycle/ path ว่ากราฟที่กำหนดให้ เป็น hamiltonian graph หรือไม่ มีแต่เพียงทฤษฎีบทรองรับบางรูปแบบของกราฟเท่านั้น เช่น ถ้าตรงตาม เงื่อนไข นี้ นี้ นี้ ก็เป็น Hamiltonian graph แต่ถ้าไม่ตรงตามนี้ ก็ยังฟันธงไม่ได้ ว่า เป็น หรือไม่

ในทาง computer science ปัญหาการหาทางเดิน hamiltonian graph ถือเป็นปัญหาที่สำคัญ และจัดอยู่ในกลุ่ม NP ซึ่งพูดง่ายๆ ก็คือยังไม่มี algorithm ดีๆ ที่เมื่อเขียนเป็นโปรแกรม แล้วจะทำงานเสร็จในเวลาที่มนุษย์คอยได้ เช่น อาจจะต้องรอเป็นหลายหมื่นหลายแสนปี กว่า โปรแกรมจะคำนวณผลเสร็จ ในกรณีที่เจอกราฟที่มีจุดมากๆ

แต่ถ้า เมื่อใด คอมพิวเตอร์แบบ quantum computer สำเร็จ ปัญหาตระกูล NP ก็จะเป็นเรื่องเล็กๆ อย่างแน่นอนครับ

รู้สึกผมจะอธิบายเพลินไปหน่อย พอดีกว่าเนอะ

คุณ passer-by อธิบายได้ละเอียดดีจัง แบบนี้ผมชอบครับ เอ...เท่าที่ผมทราบ ถึงแม้สำหรับ quantum computer เราก็ยังไม่สามารถพิสูจน์ได้ว่า NP = P นะครับ อาจมี NP-problem บางอันที่จะกลายเป็น P สำหรับ quantum computer อย่างเช่น integer factoring แต่ถ้าผมไม่ตกข่าวคิดว่าปัจจุบันนี้ปัญหาพวก NP-complete ก็ยังใช้ quantum computer จัดการไม่ได้นะครับ

อธิบายมาเสียยืดยาว มาตกม้าตาย ตอนจบซะนี่เรา

อย่างที่ คุณ 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 ไปนานแล้ว)

อยากทราบความแตกต่างของปัญหา NP , NP complete , NP Hard น่ะครับ ช่วยอธิบายพร้อมยกตัวอย่างให้ดูหน่อยนะครับ ว่ามีอะไรบ้าง
แล้วยังมี NP ชนิด อื่นอีกรึป่าวครับ :)

อ่านใน My Math ค่ะ
ละเอียดเหมือนกัน
ถูกมากสี่สีทั้งเล่ม แค่40บาท ไม่อยากจะเชื่อ

ตอบให้คร่าวๆ ระดับหนึ่งแล้วกันนะครับ

ปัญหา NP ก็คือ ปัญหาที่มนุษย์ไม่สามารถรอคอยผลได้ ด้วยการ run program บนคอมพิวเตอร์ที่ใช้กันทั่วๆไป เพราะเวลาที่ใช้คำนวณ อาจเติบโตด้วย exponential rate ของจำนวน input

บางปัญหา อาจกินเวลาเป็นหลายๆพันปี ถ้ามีข้อมูลมากๆ

แต่ NP จะ solve ให้เสร็จแบบเร็วๆ ด้วยการ run algorithm บน processor กลุ่ม nondeterministic turing machine ซึ่งไอ้เจ้า processor แบบที่ว่า เป็น คอมพิวเตอร์ใน จินตนาการ พอสมควร (อย่าถามผมต่อนะ ว่าหลักการของ turing machine ชนิดนี้เป็นยังไง อันนี้ไม่รู้จริงๆ)

สำหรับ NP hard จะมีลักษณะที่ว่า ถ้ามี algorithm ที่ solve ปัญหานี้ได้ แล้ว จะสามารถแปลง solution ไปสู่การแก้ปัญหาอื่นๆใน NP ได้ด้วย

NP hard อาจเป็น NP หรือไม่เป็นก็ได้ ตัวอย่างปัญหาที่เป็น NP hard แต่ไม่เป็น NP เช่น halting problem (More details about NP hard and halting problem)

ถ้าปัญหาใดเป็นทั้ง NP และ NP hard จะเรียกปัญหานั้นว่า NP Complete (NPC) และเพราะ NPC มีความเป็น NP hard ในตัว ดังนั้น ถ้าสามารถแก้ปัญหาใด ปัญหาหนึ่งในกลุ่ม NP complete ได้ ก็จะ สามารถ แปลง solution ดังกล่าว ไปสู่การแก้ปัญหาทุกๆ ปัญหาในกลุ่ม NP ได้ เรียกได้ว่า แก้เพียง 1 อาจแก้ได้หมดทั้ง group

ตัวอย่างปัญหา NP complete มีมากมาย เช่น การหา hamiltonian cycle ในกราฟ ที่ผมกล่าวไปแล้ว , การหากลยุทธ์ในการเล่นเกม Minesweeper (เกมใน window ที่มีระเบิด ล้อมรอบตัวเลขน่ะครับ) ,ปัญหาการบรรจุของ เช่น ควรจะใช้ thumb drive 128 MB น้อยสุดกี่อัน ถึงจะบรรจุไฟล์สารพัด size ที่มีอยู่ลงไปได้หมด ฯลฯ


ส่วน NP อื่นๆ ไม่น่าจะมีแล้วมั้งครับ

ใครอยากจะเสริมเติมแต่ง หรือจะแก้ไข ก็ตามสบายเลยนะครับ

มาดูเวอร์ชั่นของผมบ้าง และเหมือนเช่นทุกครั้งคือผมไม่ขอรับประกันความถูกต้องใดๆทั้งสิ้นนะครับ :D

ปัญหากลุ่ม P คือ ปัญหาที่แก้ได้ใน polynomial time (ซึ่งแปลว่า เราสามารถหา polynomial p(n) มาอันนึงที่ทำให้เวลาที่ใช้ในการแก้ปัญหาที่มีขนาด n มีค่าน้อยกว่า p(n) ได้สำหรับทุกจำนวนเต็ม n แต่ปกติมักใช้ big O notation กันครับ) อย่างเช่นการคูณเลข n bits 2 ตัวเข้าด้วยกันโดยใช้การคูณแบบธรรมดาจะใช้เวลา O(n²) ดังนั้นปัญหาการคูณเลขจึงอยู่ในกลุ่ม P

ปัญหากลุ่ม NP คือ ปัญหาที่เราสามารถเช็คได้ว่าคำตอบที่ให้มาถูกต้องหรือไม่ได้ใน polynomial time ครับ ดังนั้น \(P\subseteq NP\) แต่มีปัญหา NP บางอันที่เราไม่รู้ว่าเป็น P รึเปล่า (นั่นคือเราไม่รู้ว่า P = NP ไหม) ตัวอย่างเช่น ปัญหา integer factoring ปัจจุบันนี้เรายังไม่รู้จัก algorithm ใดที่สามารถแยกตัวประกอบของจำนวนเต็ม N ได้ใน polynomial time แต่เราสามารถเช็คคำตอบว่า N = ab จริงมั้ยได้ใน polynomial time ดังนั้น ปัญหา integer factoring จึงอยู่ใน NP แต่(ยัง?)ไม่อยู่ใน P ซึ่งเราเรียกปัญหาพวกนี้ว่า NP-hard ครับ

NP-complete เป็น subset พิเศษของ NP-hard ปัญหาในกลุ่มนี้ equivalent กันหมดครับ คือถ้าแก้ได้อันนึงก็แก้อันอื่นๆได้หมด จะว่าไปแล้ว NP-complete ก็คือกลุ่มของปัญหาทั้งหมดที่ equivalent กับปัญหาการหา Hamiltonian cycle นั่นเอง ปัญหาที่เป็น NP-hard แต่ไม่เคยมีใครพิสูจน์ว่าเป็น (และจริงๆแล้วก็ไม่น่าจะเป็น) NP-complete ก็เช่น integer factoring ครับ

แม้ปัจจุบันนี้ ปัญหา integer factoring จะเป็น NP-hard สำหรับ conventional computer (ที่เราเรียกกันว่า Turing machine) แต่จะเป็น P สำหรับ (hypothetical) quantum computer เนื่องจากการค้นพบ Shor's algorithm เมื่อไม่นานมานี้ นั่นคือถ้ามีคนสร้าง quantum computer ได้เมื่อไหร่การเข้ารหัสแบบที่เราใช้กับ https:// ในปัจจุบันก็จะหมดประโยชน์ไปเลยครับ

ผมได้ตัดต่อ และเพิ่มเติมอะไรเข้าไปนิดหน่อย ในคำอธิบายของผมข้างบน

ส่วน version คุณ warut อันนี้ ผมเห็นด้วยทั้งหมดครับ ยกเว้น ที่บอกว่า integer factoring เป็น NP hard

หรือว่านิยาม NP hard ของผมกับคุณ warut ไม่เหมือนกัน ก็ไม่รู้

ในความเห็นส่วนตัวของผม integer factoring น่าจะเป็นแค่ NP เท่านั้นนะครับ