ในบรรดาปัญหาคณิตศาสตร์ 7 ปัญหาแห่งสหัสวรรษ ปัญหาที่ชื่อว่า P versus NP เขียนย่อว่า P vs NP เป็นปัญหาที่ยอมรับกันในวงกว้างว่าเป็นปัญหาเปิดที่ลึกซึ้งที่สุดของคณิตศาสตร์
เมื่อเทียบกับปัญหาชิงเงินล้านอื่นๆเช่น Riemann Hypothesis ซึ่งเกี่ยวกับการกระจายตัวของจำนวนเฉพาะกับ the zeta function ที่มีผู้เสนอคำตอบเพื่อให้นักคณิตศาสตร์ตรวจสอบไปเร็วๆนี้ (อ่านเพิ่มได้จากเพจ ฟิสิกส์หมาหมา[ที่นี่]) หรือปัญหา Poincare Conjecture ซึ่งแก้โดยนักคณิตศาสตร์สุดอัจฉริยะสุดสมถะ Grigori Perelman ซึ่งได้ปฏิเสธเงินรางวัลไปเป็นที่เรียบร้อย! หรือปัญหาเกี่ยวกับสภาวะปั่นป่วนของคำตอบสมการของไหล Navier-Stokes ซึ่งผู้อ่านสามารถทำการทดลองสังเกตความยากและความมหัศจรรย์ของปัญหานี้ได้เองที่บ้าน (อ่านเพิ่มได้จากเพจ Sciamese Ket [ที่นี่]) ปัญหา P vs NP นั้นน่าจะลึกซึ้งกว่าปัญหาทั้งหมด
จำนวนเฉพาะ ทรงกลม ของไหลอย่างอลหม่านปั่นป่วน เป็นวัตถุที่สำคัญทางคณิตศาสตร์และทางธรรมชาติ ปัญหาเกี่ยวกับวัตถุเหล่านี้นั้นลึกและยาก หากแต่ว่า P vs NP เป็นปัญหาเกี่ยวกับธรรมชาติของการแก้ปัญหา เป็นปัญหาของวิธีการแก้ปัญหา ล้ำไปอีกขั้น สรุปข้อความสั้นๆได้ว่า
การหาคำตอบ กับ การตรวจสอบคำตอบ อันไหนยากกว่ากัน?
นอกจากผู้ที่แก้ได้จะได้รับเงินหนึ่งล้านเหรียญสหรัฐแล้ว มนุษยชาติยังจะต้องปรับเปลี่ยนวิถีชีวิตตามคำตอบของปัญหานี้กันเลยทีเดียว
ในตอนนี้ทีม QuTE จะขยายความของคำถามข้างต้น อธิบายว่า “ยาก” ในที่นี้หมายความว่าอะไร จะแนะนำตัวละครที่สำคัญสองตัวคือ คุณ P กับ คุณ NP ว่าเขาคือใคร แล้วจะอธิบายว่าปัญหา P versus NP คืออะไร และมนุษยชาติคิดว่า P กับ NP นี้มีความสัมพันธ์กันอย่างไร
ความซับซ้อนของวิธีการหาคำตอบ (Algorithmic Complexity)
ก่อนจะแนะนำคุณ P กับ คุณ NP เราจะเกริ่นถึงความสำคัญของความซับซ้อนในการคำนวณ (Algorithmic Complexity หรืออีกชื่อคือ Computational Complexity) ซึ่งเป็นพื้นฐานสำหรับทำความเข้าใจปัญหา P vs NP เราจะยกตัวอย่างให้เห็นภาพจากปัญหาง่ายๆ หากบวกลบคูณหารเป็นก็จะเข้าใจได้ ดังนี้
Multiplying Prime Numbers ( encryption )
สมมติเราอยากฝึกสมองคูณจำนวนเฉพาะ n = 2 หลัก สองจำนวน เพื่อหาคำตอบของ
19 X 31 = ?
เนื่องจากเราท่องสูตรคุณแม่ 19 ไม่ได้ จึงต้องคูณกระจายแต่ละหลัก จากนั้นจึงบวกเลขให้ตรงหลักอย่างที่เรียนกันในระดับอนุบาล สมองใครคิดเร็วอาจใช้เวลาเสี้ยววินาทีในการพบคำตอบคือ 589
ทีนี้ถ้าเราต้องคูณจำนวนเฉพาะ n = 15 หลัก สองจำนวนดังต่อไปนี้
314159265358979 X 271828182845904 = ?
วิธีคูณกระจายและบวกเลขให้ตรงหลักพร้อมกระดาษทดและปากกา ยังทำให้พบคำตอบได้เช่นเคย (แต่ต้องใช้เวลาและความอดทนเพิ่มขึ้น) คำตอบคือ 85397342226735418150399772016
จากสองกรณีตัวอย่างนี้ สังเกตได้ว่า ไม่ว่า n จะใหญ่เท่าใด เราสามารถหาคำตอบของปัญหาการคูณจำนวนเฉพาะ n หลัก สองจำนวน ด้วยการคูณกระจายและบวกเลขให้ตรงหลัก จำนวนขั้นตอนในการคูณและบวกเพื่อให้ได้มาซึ่งคำตอบจะขึ้นกับขนาด n ยิ่ง n ใหญ่ ยิ่งมีจำนวนขั้นตอนการคำนวณมากขึ้น วิธีอนุบาลที่ติดตัวเรามามีจำนวนขั้นตอนคำนวณโดยประมาณ n2 ขั้นตอน
ถ้าเราหาคำตอบได้ เราก็สามารถสั่งงานคอมพิวเตอร์ให้ปฏิบัติตามขั้นตอนที่สมองทำงานร่วมกับกระดาษและปากกาได้เช่นกัน จำนวนขั้นตอนที่คอมพิวเตอร์หาคำตอบก็จะโตตาม n2 เช่นกัน หากแต่ว่าหนึ่งขั้นตอนการคำนวณของคอมพิวเตอร์ใช้เวลาน้อยนิด การหาคำตอบของปัญหา n = 15 อาจใช้เวลาเศษเสี้ยววินาที เทียบกับสมองมนุษย์ซึ่งคิดช้าอาจใช้เวลาหลายนาที
ในทางเทคนิค การหาคำตอบปัญหาการคูณจำนวนเฉพาะ n หลัก สองตัว ด้วย “อัลกอริทึม”การคูณแบบอนุบาล หรือพูดภาษาบ้านๆคือ “วิธีการ”คูณแบบอนุบาล นั้น เราเรียกว่าการหาคำตอบด้วย “อัลกอริทึมแบบพหุนาม” (polynomial-time algorithm) ซึ่งแสดงด้วยสัญลักษณ์ “Big O” ว่า O(nk) โดยที่ k เป็นจำนวนเต็มบวกใดใด ( k = 2 สำหรับการคูณแบบอนุบาล) สัญลักษณ์ O(nk) นี้สื่อความหมายว่า เมื่อ n ใหญ่ๆ จำนวนขั้นตอนของอัลกอริทึมในการหาคำตอบจะโตตามขนาดของ input ยกกำลัง k
นักคณิตศาสตร์และนักวิทยาการคอมพิวเตอร์ที่ศึกษาความซับซ้อนในการคำนวณ ให้ความสำคัญเป็นอย่างสูงกับ Big O เนื่องจากมันแสดงถึงประสิทธิภาพในการหาคำตอบของอัลกอริทึม ถ้าจำนวนขั้นตอนของอัลกอริทึมในการหาคำตอบ โตเร็วตามขนาด input n กว่าการโตแบบพหุนาม ( เช่น O(kn) โดยที่ k เป็นจำนวนจริงที่มากกว่าหนึ่ง ซึ่งเรียกว่าการโตแบบทวีคูณ (exponential-time algorithm) ) แทบจะเป็นไปไม่ได้เลยที่คอมพิวเตอร์จะหาคำตอบสำหรับ n ใหญ่ๆได้พบในเวลาที่จำกัด
จากรูปนี้ จะเห็นได้ว่าการโตแบบพหุนามนั้น โตช้ากว่าการโตแบบทวีคูณเมื่อ n ใหญ่ๆ อัลกอริทึมที่มีความซับซ้อนในการหาคำตอบซึ่งโตแบบพหุนามตามขนาด input n นั้นเปรียบเสมือนจอกศักดิ์สิทธิ์สำหรับวงการวิทยาการคอมพิวเตอร์ คอมพิวเตอร์ที่มีความเร็วสูงมากมีโอกาสจะหาคำตอบได้พบในเวลาไม่มากจนเกินไปแม้ n จะใหญ่มาก นั่นคือถ้าสามารถประดิษฐ์อัลกอริทึมซึ่งหาคำตอบได้แบบ O(nk) โดยที่ k ไม่ใหญ่นัก เรามีโอกาสที่จะทราบคำตอบของปัญหาได้ในเวลาไม่นานจนเกินไป สรุปสั้นๆว่า
polynomial-time algorithm เริ่ด แต่ exponential-time algorithm เละ….
สำหรับการคูณหาคำตอบของสองจำนวนขนาด n หลักใหญ่ๆที่ใช้กันในปัจจุบัน มีผู้ประดิษฐ์อัลกอริทึมที่เหนือกว่าวิธีอนุบาลที่เราคุ้นเคย ทำให้ลดจำนวนขั้นตอนไปได้มาก ยกตัวอย่างเช่นวิธี Fast Fourier Transform มีจำนวนขั้นตอนซึ่งโตแบบ O(n log(n) log(log(n))) [2] หรือวิธี Karatsuba algorithm มีจำนวนขั้นตอนซึ่งโตแบบ O(nlog23 ) ≈ O (n1.585) [3] ทั้งสองอัลกอริทึมนี้ทำให้พบคำตอบได้เร็วกว่าวิธีอนุบาลที่มีจำนวนขั้นตอนโตแบบ O(n2)
Prime Factorization (decryption)
ในกรณีที่เราต้องการแก้ปัญหาย้อนกลับของการคูณจำนวนเฉพาะ ซึ่งคือการแยกตัวประกอบเป็นจำนวนเฉพาะ (Prime Factorization) อันเป็นหัวใจสำคัญของระบบความปลอดภัยแบบ RSA ที่ถูกกล่าวถึงในบทความ [QuTE-การเข้ารหัสทางควอนตัม]
จากผลคูณข้างต้น เราสามารถตั้งปัญหาย้อนกลับ คือจงแยกตัวประกอบเป็นจำนวนเฉพาะสองตัวคูณกันของ
589 = ? X ?
วิธีการตรงไปตรงมา ก็คือลองผิดลองถูกค้นหาจำนวนซึ่งหาร 589 ให้เหลือเศษศูนย์ โดยอาจจะไล่ตัวหารจำนวนเฉพาะจากน้อยไปมาก จากหารด้วย 2 ลองหารด้วย 3 ลองหารด้วย 5 … จนพบว่าหารด้วย 19 จะเหลือเศษศูนย์ เราจะพบตัวประกอบอีกตัวทันทีคือ 31
ถ้าใช้วิธีเดียวกันเพื่อหาคำตอบของ
85397342226735418150399772016 = ? X ?
การเริ่มตัวหารจากจำนวนเฉพาะที่น้อยคือ 2 แล้วไล่ตัวหารไปตัวที่ใหญ่ขึ้น จนพบตัวหารที่ให้เศษศูนย์ ขั้นตอนการเดาแบบนี้จะต้องทดลองค้นหาตัวหารเป็นอย่างน้อย 1014 ครั้ง จนกระทั่งเจอ 271828182845904 ที่ทำให้การหารเหลือเศษศูนย์ ซึ่งเป็นตัวประกอบที่เล็กที่สุด (เมื่อเทียบกับ 314159265358979)
สังเกตได้ว่า จำนวนขั้นตอนเพื่อหาคำตอบจะโตตามขนาด input แบบไม่ค่อยมีประสิทธิภาพในการหาคำตอบเท่าไหร่ เป็นปัญหาที่ยากจะพบคำตอบได้ด้วยการลองผิดลองถูก
แม้มนุษย์จะประดิษฐ์อัลกอริทึมที่ดีกว่าการลองผิดลองถูกออกมาเรื่อยๆ อัลกอริทึมเพื่อแก้ปัญหา prime factorization ด้วย classical computer ก็ยังไม่สามารถแยกตัวประกอบได้ในเวลาแบบพหุนามอยู่ดี
การนำจำนวนเฉพาะขนาดใหญ่ สมมติเป็นเลข 100 หลัก สองตัวมาคูณกัน ใช้ขั้นตอนคำนวณประมาณหมื่นขั้นตอน แต่ถ้าเรานำคำตอบของการคูณนี้มาแยกตัวประกอบ จำนวนขั้นตอนในการคำนวณจะประมาณหนึ่ง google – เลขหนึ่งที่มีศูนย์ตามร้อยตัว – ซึ่งเป็นจำนวนที่มากกว่าค่าประมาณของจำนวนอิเล็กตรอนในจักรวาลนี้ (ประมาณเลขหนึ่งตามด้วยศูนย์ 79 ตัว…)…
ในปี 2012 มนุษย์สามารถแยกตัวประกอบของจำนวน 212 หลักที่ชื่อว่า RSA-704 ได้สำเร็จ โดยใช้ทั้งอัลกอริทึมขั้นสูงและคอมพิวเตอร์ที่มีประสิทธิภาพสูงหลายเครื่อง หากแต่อัลกอริทึมที่แอดวานซ์สุดนี้ยังต้องใช้เวลาถึง 20 years of computer time ในการหาคำตอบ [อ่านผลงานวิจัยและรายละเอียดได้ที่นี่]
prime factorization สำหรับตัวเลขใหญ่เป็นปัญหาที่ ยาก คือยังไม่มี polynomial-time algorithm ซึ่งหาคำตอบได้ การคูณจำนวนเฉพาะขนาดใหญ่มีอัลกอริทึมทำได้เร็ว แต่การแยกตัวประกอบผลคูณนั้นยังไม่พบอัลกอริทึมที่เร็วพอ เราจึงใช้ประโยชน์ของความไม่สมมาตรระหว่างสองอัลกอริทึมนี้เพื่อสร้างระบบความปลอดภัยแบบ RSA ซึ่งมีการเข้ารหัสด้วยการคูณ (encrypt เร็ว) และการถอดรหัสด้วยการแยกตัวประกอบ (decrypt ช้า) อ่านประวัติ RSA challenge problems เพิ่มเติมได้[ที่นี่]
ปัญหานี้เป็นตัวอย่างที่แสดงว่า แม้เราจะสร้างคอมพิวเตอร์พลังสูงจำนวนมากมาช่วยคำนวณ เราก็มิอาจตอบปัญหาคณิตศาสตร์ที่เราสนใจได้ในเวลาจำกัดหากความซับซ้อนของอัลกอริทึมในการหาคำตอบนั้นโตเร็วกว่าแบบพหุนาม การถึกลุยงมเข็มในมหาสมุทร (หรือการงมหาเด็กติดถ้ำหลวง?) อาจใช้เวลามากกว่าอายุขัยของจักรวาลเพื่อควานหาเข็มก็เป็นได้
แล้วปัญหาใดที่คอมพิวเตอร์สามารถ แก้ได้ หรือ ยังแก้ไม่ได้ อย่างมีประสิทธิภาพในเวลาจำกัด?
นี่คือคำถามซึ่งนำไปสู่ตัวละครสองตัวคือ P กับ NP ที่เราจะแนะนำ
P vs NP คือปัญหาของการแก้ปัญหา
เราได้เกริ่นถึงความสำคัญของ polynomial-time algorithm ว่าเป็นอัลกอริทึมที่ เร็ว ในการหาคำตอบ แน่นอนว่ามีปัญหาอื่นอีกมากมายที่คำตอบสามารถพบได้ด้วย polynomial-time algorithm เช่น การบวกเลขจำนวนใหญ่ๆ หรือ การค้นหาพารามีเตอร์เพื่อหาค่าสูงสุด (หรือต่ำสุด) ของ convex function ด้วย Linear Programming ที่พบเจอได้บ่อยใน Operation Research และ Convex Optimization
กลุ่มของปัญหาที่เราพบอัลกอริทึมค้นหาคำตอบโดยจำนวนขั้นตอนของอัลกอริทึมโตแบบพหุนาม (มี polynomial-time algorithm ในการหาคำตอบ) เรียกว่ากลุ่มปัญหา P (Polynomial Time)
ส่วนกลุ่มของปัญหาซึ่งถ้าเราถูกหยิบยื่นคำตอบให้ตรวจสอบความถูกต้อง เราสามารถจะตรวจสอบความถูกต้องคำตอบของปัญหาได้ด้วย polynomial-time algorithm เรียกว่ากลุ่มปัญหา NP (Non-deterministic Polynomial Time)
จากคำจำกัดความนี้ กลุ่มปัญหา P เป็นสับเซตของกลุ่มปัญหา NP (P ⊆ NP) เพราะปัญหาใดก็ตามที่แก้ได้ด้วย polynomial-time algorithm วิธีการตรวจสอบคำตอบของปัญหาก็คือการแก้ปัญหานั่นแหละ จึงทำให้วิธีการตรวจสอบคำตอบเป็น polynomial-time algorithm ไปด้วย
ในทางกลับกัน กลุ่มปัญหา NP เป็นสับเซตของกลุ่มปัญหา P หรือไม่? เป็นคำถามที่ยังไม่มีใครตอบได้ เพราะหากกล่าวถึงปัญหาที่มนุษย์ยังไม่พบวิธีการค้นหาคำตอบได้ใน polynomial time แต่ตรวจสอบคำตอบได้ใน polynomial time เราจะรู้ได้อย่างไรว่ามีอัลกอริทึมอันรวดเร็วเพื่อหาคำตอบของปัญหานั้นอยู่ไหม? เป็นคำถามที่ยาก เพราะคล้ายการงมเข็มในมหาสมุทรโดยเราไม่ทราบว่าในมหาสมุทรมีเข็มไหม!
ปัญหาเปิดชิงเงินล้านเหรียญที่เราเกริ่นนำมานานในตอนนี้ก็คือปัญหาที่ว่า [5]
P = NP หรือไม่ ?
เนื่องจาก P ⊆ NP นั้นชัดเจน แต่การจะพิสูจน์ว่า NP ⊆ P หรือว่า NP ⊄ P เป็นเรื่องยาก คำตอบของ P vs NP จึงลดทอนเหลือคำตอบของปัญหาสุดหินที่ว่า
ถ้าตรวจสอบคำตอบได้ด้วย polynomial time แล้วจะ ค้นหาคำตอบได้ด้วย polynomial time ไหม?
ซึ่งโพลผลโหวตในปี 2002 จากผู้เชี่ยวชาญพบว่า 61% เชื่อว่า NP ⊄ P ทำให้ P ≠ NP [ที่มา] โดยบางคนคาดคะเนว่าคณิตศาสตร์ปัจจุบันยังไม่เหมาะสม อาจใช้เวลาอีกนับร้อยปีกว่ามนุษยชาติจะแก้ปัญหานี้ได้!
กลุ่มปัญหา NP-Complete
แล้วเราจะพูดกว้างๆถึงกลุ่มปัญหาและนิยามการค้นหากับการตรวจสอบให้งงไปทำไม? เจาะจงการหาคำตอบของปัญหาใดปัญหาหนึ่งน่าจะง่ายกว่าไหม ?
สาเหตุที่นิยามงงเช่นนี้ยังคงอยู่ ก็เพราะทฤษฎีมหัศจรรย์ของ Stephen Cook กับ Leonid Levin (Cook-Levin theorem ที่ออกสู่สายตาชาวโลกในช่วงปี 1970) ซึ่งกล่าวว่า
ปัญหาใดใดใน NP สามารถลดทอน(ด้วยเวลา polynomial time) สู่ปัญหาการทดสอบประโยค boolean ว่าเป็นจริงได้ไหม!!
ปัญหาการตรวจสอบว่า boolean formula เป็นจริงได้ไหม ( Boolean Satisfiability Problem (SAT) ) คือการหาคำตอบว่าประโยคทางตรรกศาสตร์ที่ประกอบด้วย boolean variable xi ∈ { จริง , เท็จ } สามารถเป็นจริงได้ไหม เช่นประโยค x1 ∧ x2 เป็นจริงได้ถ้า x1 และ x2 เป็นจริงทั้งคู่ หรือ เท็จทั้งคู่ ประโยคนี้ satisfiable ส่วนประโยค x1 ∧ ¬ x1 เป็นเท็จไม่ว่า x1 จะมีค่าความจริงอะไรก็ตาม ประโยคนี้ unsatisfiable
ความเทพของ Cook-Levin theorem ทำให้นิยามที่ดูไร้ประโยชน์ของกลุ่มปัญหา P กับ NP มีประโยชน์ขึ้นมามหาศาล เพราะหากเราตอบได้ว่า SAT มี polynomial-time algorithm ที่ใช้ตอบปัญหาหรือปล่าว เราจะรู้ทันทีว่า NP ⊆ P นั้นจริงไหม นั่นคือปัญหา P vs NP จะถูกแก้โดยทันที!
ซึ่งหมายความว่า เราจะรู้ทันทีว่ามีอัลกอริทึมแบบพหุนามไหม ที่สามารถแก้ปัญหา prime factorization ข้างต้น เพราะ prime factorization เป็นปัญหา NP ( ถ้าเรามีจำนวนเฉพาะสองตัว เราสามารถคูณจำนวนสองตัวนั้นเพื่อตรวจสอบความถูกต้องของคำตอบด้วย polynomial-time algorithm ระดับอนุบาล แต่มนุษย์ยังไม่พบอัลกอริทึมในการแยกตัวประกอบแบบ polynomial time เราจึงไม่รู้ว่าปัญหานี้อยู่ในกลุ่ม P หรือปล่าว)
หากเราทราบว่าปัญหา SAT เป็นหรือไม่เป็นปัญหา P เราก็จะรู้ทันทีว่า prime factorization เป็นหรือไม่เป็นปัญหา P ไปด้วย ความปลอดภัยในการเข้ารหัสและถอดรหัสของสังคมมนุษย์ จึงอยู่ในกำมือของ SAT!
หลังจากเราทราบว่าทุกๆปัญหา NP สามารถลดทอนลงสู่ปัญหา SAT ได้ใน polynomial time ปัญหาอื่นๆที่ NP สามารถลดทอนลงสู่ได้ด้วย polynomial time ก็ผุดโผล่ขึ้นมาอีกมากมาย กลุ่มปัญหา NP เหล่านี้ ซึ่งถ้าพิสูจน์ได้ว่ามีหรือไม่มี polynomial-time algorithm ในการหาคำตอบ จะแก้ปัญหาเปิด P vs NP ได้ทันทีนั้น เรียกว่ากลุ่มปัญหา NP-Complete หรือเขียนสั้นๆว่า NPC
นอกจาก SAT แล้ว ปัญหาอื่นในกลุ่ม NP-Complete (ดูลิสต์ของปัญหาที่มนุษย์ทราบ[ ที่นี่ ] ) ที่เราคงคุ้นเคยกันมากที่สุดคือปัญหา Traveling Salesman Problem (decision version)
สรุปสั้นๆแบบสีจืดๆ
เราทราบว่า P ⊆ NP แต่ NP ⊆ P หรือไม่เราไม่รู้ หนึ่งในแนวทางพิสูจน์ว่า NP ⊆ P หรือไม่ ทำได้ด้วยการพิสูจน์ว่าปัญหาใดปัญหาหนึ่งในกลุ่ม NP-Complete อยู่ใน P หรือไม่ นั่นคือเจาะจงไปที่ปัญหาใดปัญหาหนึ่ง เช่น SAT (ซึ่งเป็นปัญหาแรกที่พิสูจน์ด้วย Cook-Levin theorem ว่าเป็น NP-Complete) จากนั้นจึงพยายามพิสูจน์ว่ามี(หรือไม่มี) polynomial-time algorithm ในการหาคำตอบของปัญหานั้น
สรุปสั้นๆแบบ PPAP
อย่างไรก็ตามผู้เชี่ยวชาญเช่น Richard Karp เจ้าพ่อ Traveling Salesman problem เจ้าของรางวัล Turing Award ซึ่งเป็นเหมือน Nobel prize for computer science เชื่อว่าวิธีการเจาะจงปัญหาหนึ่งปัญหาใน NPC เพื่อพิสูจน์ว่าปัญหานั้นอยู่ใน P หรือไม่ แม้จะเป็นวิธีที่น่าสนใจ แต่อาจไม่ใช่วิธีตอบปัญหา P vs NP (> <)
กลุ่มปัญหาอื่นๆและความสำคัญของ P vs NP
ที่กล่าวมาทั้งหมดคือกลุ่มปัญหาที่ใช้ deterministic algorithm ไม่มี randomized algorithm ที่นักฟิสิกส์และนักเคมีคุ้นเคยในการ optimize ด้วย simulated annealing ไม่มีอัลกอริทึมที่บางครั้งการตรวจสอบคำตอบด้วย polynomial-time algorithm ก็ยังทำไม่ได้ นักวิทยาการคอมพิวเตอร์ได้จัดกลุ่มความซับซ้อนของการคำนวณด้วยแผนภาพ Venn คร่าวๆดังนี้
ยังมีกลุ่มปัญหาที่กระบวนการแก้ปัญหามีความแตกต่างอีกมากมายที่เรายังไม่ได้กล่าวถึงในบทความนี้
แต่สาเหตุที่เราให้ความสนใจกับ P vs NP มากกว่าชาวบ้าน ก็เพราะมีปัญหา NP หลายปัญหาที่มีบทประยุกต์สำคัญกับมนุษยชาติ เช่น
- การแยกตัวประกอบที่เกิดจากการคูณกันของจำนวนเฉพาะขนาดใหญ่ ซึ่งเป็นพื้นฐานความปลอดภัยของรหัส RSA
- การเข้าใจเส้นทางการพับของโปรตีนจากลำดับการจัดเรียงของโมเลกุล ซึ่งอาจช่วยแนะวิธีรักษาโรคร้ายหลากชนิดได้
- การค้นหาลำดับย่อยในลำดับ DNA ขนาดใหญ่ ซึ่งช่วยให้เราศึกษาชีววิทยาและศึกษาวิธีการรักษาโรคได้รวดเร็วและแม่นยำขึ้น
- การจัดตารางการเดินรถ ตารางการทำงาน ตารางการผลิต ในสาขา Operation Research และ Mechanism Design ซึ่งช่วยลดต้นทุนและเพิ่มประสิทธิภาพในหลากหลายแง่มุมของสังคมมนุษย์
- การหา ground state (สถานะของกลุ่มของสปินที่มีพลังงานต่ำสุด) ใน Ising model ที่มี disordered and long-range interaction (spin-glass) ซึ่งมีความประพฤติคล้ายกับ อัลกอริทึมการเรียนรู้ด้วย Deep Learning ที่เป็นวิธียอดนิยมของ computer vision ในปัจจุบัน
เป็นต้น
การตอบปัญหาว่า การหาคำตอบ กับ การตรวจสอบคำตอบ อันไหนยากกว่ากัน? ( โดยคำว่ายากในที่นี้หมายถึง ทำไม่ได้ใน polynomial-time ) จะช่วยให้มนุษย์ทราบว่า ระบบความปลอดภัยของรหัสในปัจจุบันนั้นดีพอไหม เรามีโอกาสจะรักษาโรคร้ายเช่นมะเร็งไหม มนุษย์มีโอกาสจะสร้างคอมพิวเตอร์ที่มีระบบการมองเห็นแบบเมพสุดๆได้หรือไม่ หรือแม้แต่เราสามารถสร้างคอมพิวเตอร์ซึ่งตรวจสอบบทพิสูจน์ทฤษฎีคณิตศาสตร์โดยอัตโนมัติได้ไหม
วิถีชีวิตของมนุษยชาติคงต้องเปลี่ยนแปลงตามคำตอบของมหากาพย์ปัญหาแห่งสหัสวรรษ P vs NP
การเข้ามาของควอนตัมคอมพิวเตอร์
ปัญหาที่กล่าวมาทั้งหมดข้างต้น มีพื้นฐานมาจากการคำนวณด้วย classical computer หากเราสามารถสร้างควอนตัมคอมพิวเตอร์ได้ ขอบเขตของปัญหาที่แก้ได้ด้วย polynomial-time ก็จะกว้างขึ้น ดั่งเช่นแผนภาพ Venn นี้
ในตอนต่อๆไปเราจะมาเล่าให้ฟังว่าปัญหา NP อะไรบ้างที่แก้ได้ด้วยควอนตัมคอมพิวเตอร์อย่างมีประสิทธิภาพ ติดตามกันตอนหน้าๆนะจ๊ะ ( ใครอยากจะชะโงกทัวร์ว่าอัลกอริทึมควอนตัมเป็นอย่างไรในฉบับภาษาไทย ตามอ้างอิง [4] ไปเลยจ้า )
เรียบเรียงโดย SCiamese Ket
อ้างอิง
[1] M. Sipser, The History and Status of the P versus NP Question, Annual ACM STOC, 1992
[2] C. Moore, S. Merten, The Nature of Computation, Oxford University Press, 2011
[3] Wikipedia: P versus NP problem
[4] ตามอ่านบทความภาษาไทยซึ่งเพิ่มเติมเรื่องความสำคัญของ computational complexity และหลักการของรหัส RSA ไว้ได้ดี รวมถึงอธิบายหลักการและประสิทธิภาพของอัลกอริทึมควอนตัมไว้ได้ [ที่นี่]
[5] อ่านข้อความของปัญหาฉบับเต็ม จาก Clay Mathematics Institute ได้ [ที่นี่] – จะได้ทราบว่าบทความนี้นี่ย่อยมาให้อ่านง่ายมากแล้วนะจ๊ะ
ปล. บทสัมภาษณ์ปรมาจารย์สาย computational complexity
คำตอบของ P vs NP น่าจะออกมาลักษณะใด จะแก้ได้เมื่อไหร่ อย่างไร? [ที่มา]
