เกี่ยวกับปัญหา P กับ NP

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

สำหรับคนที่เคยผ่านหูผ่านตาปัญหาชื่อประมาณนี้มาบ้าง ขอผมทบทวนสักหน่อยโดยใช้ภาษาที่ไม่เป็นทางการนัก

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

ปัญหานี้เป็นเรื่องพื้นฐานมาก ๆ ของการหาคำตอบ กับการยืนยันคำตอบ ซึ่งหลาย ๆ คนเชื่อกันว่า อย่างหลังน่าจะง่ายกว่า

ผมจำได้ว่าได้อ่านจาก โพล ที่ทำโดย William Gasarch เกี่ยวกับปัญหา P และ NP คำตอบหนึ่งของ Luca Trevisan ในโพลนั้น (ที่หลาย ๆ คนคงคิดคล้าย ๆ กับเขา) ก็คือ เขากลัวว่าการพิสูจน์ปัญหาดังกล่าวจะเกิดจากการที่บางคนสังเกตเห็นความเกี่ยวข้องบางอย่างระหว่างปัญหานี้กับคณิตศาสตร์แปลก ๆ แล้วก็พิสูจน์ปัญหานี้ออกมาโดยการทำงานในคณิตศาสตร์แปลก ๆ นั้น แล้วเราซึ่งเป็นนักวิทยาการคอมพิวเตอร์ซึ่งรู้เรื่องแค่คอมบินาทอริคส์ จะไม่มีทางเข้าใจบทพิสูจน์นั้นเลย

(ผมได้ข่าวจากบล็อกของ Luca) ในงานการประชุมนักคณิตศาสตร์นานาชาติที่กรุงมาดริก (ICM'06) ที่จะถึงนี้ Avi Wigderson จะนำเสนอบทความ ที่สรุปความคืบหน้าของการพิสูจน์ปัญหา P กับ NP ตอนต้นบทความเขาอ้างถึงคำพูดของ Steve Smale ว่า "ปัญหา P กับ NP --- ของขวัญสำหรับคณิตศาสตร์จากวิทยาการคอมพิวเตอร์"

เราอาจได้เห็นความคืบหน้าบางอย่าง และสิ่งที่ Luca กลัวที่สุดอาจเป็นจริงก็ได้

Comments

Parinya Chalermsook said…
อืม เกี่ยวกับเรื่องการแก้ปัญหา P vs NP ด้วยคณิตศาสตร์แปลกๆอะ ผมก็เห็นที่ Mulmuley ทำอยู่เหมือนกันอะ ... คนอ่านต้องเข้าใจ Lie Group, Commutative Algebra, Combinatorics, Quantum Group, Algebraic Geometry ก่อนอะ เพื่อนเล่าให้ฟังว่าพวก CS theorist ไม่ยอมรับกันหรอกนะ เพราะอ่านไม่รู้เรื่องด้วย แล้วก็การแก้ปัญหาแบบนี้มันไม่ intuitive ด้วยอะ

คิดแล้วคงเศร้าๆ ถ้ามีคน prove P NP ได้ แต่เราดันอ่านไม่รู้เรื่อง T.T
12:51 AM
Anonymous said…
ตลก น่า, ทำไม ต้อง แบ่งแยก ว่า ใคร เป็น com sci ใคร เป็น math sci ด้วย
information theory ก็ ใช้ ทฤษฎี เดียว กับ thermodynamic ไม่ใช่ เหรอ
1:33 AM
Post a Comment

Popular posts from this blog

ทฤษฎีบทขีดจำกัดกลาง (1)

Image
กฎแห่งจำนวนมาก บอกกับเราว่า ถ้าข้อมูลตัวอย่างที่สุ่มมามีจำนวนมาก ค่าเฉลี่ยที่ได้ก็จะใกล้กับค่าเฉลี่ยจริง ๆ ทฤษฎีบทขีดจำกัดกลาง (Central Limit Theorem) ให้ข้อมูลที่มากขึ้นกับเรา นั่นคือ ลักษณะของการแจกแจงของค่าเฉลี่ยที่ได้เป็นอย่างไร Central Limit Theorem กล่าวว่าการแจกแจง (distribution) ของค่าเฉลี่ยเมื่อจำนวนข้อมูลที่สุ่มมามีจำนวนมากจะเข้าใกล้การแจกแจงปกติ (Normal distribution) ซึ่งจะมีรูปโค้งเป็นแบบระฆังคว่ำ (สุดฮิต) ดังรูปด้านล่าง (รูปจาก วิกิพีเดีย ) ในรูปแสดงกราฟการแจกแจงปกติที่ค่าเฉลี่ยและความแปรปรวนต่าง ๆ กัน ค่าความหนาแน่นน่าจะเป็นของตัวแปรสุ่มที่มีการแจกแจงปกติซึ่งมีค่าเฉลี่ย $\mu$ และความแปรปรวน $\sigma^2$ คือ $f(x) = 1/(\sigma\sqrt((2\pi)))\exp(-\frac{(x-\mu)^2}{2\sigma^2})$ การแจกแจงปกตินี้ถูกนิยามขึ้นโดย Abraham de Moivre (ราชบัณฑิตเรียกเขาว่า เดอมัวฟวร์) ซึ่งใช้การแจกแจงนี้ในการประมาณค่าของการแจกแจงทวินามของจำนวนครั้งที่โยนเหรียญได้หัวจากการโยนเหรียญที่เป็นกลาง 1800 ครั้ง จากนั้น Laplace ได้ขยายทฤษฎีของ de Moivre ให้ใช้ได้กับการแจกแจงทวินามใด ๆ ถ้าเราทดลองแบบสุ่มไม่...
Read more

การสร้างรากฐานรัฐด้วยการศึกษา

ที่แอลเอ หน้าประตูเข้าสวนกุหลาบ หน้าบริเวณจัดแสดงใหญ่ ที่เป็นที่ตั้งของพิพิธภัณฑ์ประวัิติศาสตร์ธรรมชาติ (Natural History Museum) และศูนย์วิทยาศาสตร์ (Science Center) มีเสาประตูสองอันสลักเป็นประโยคว่า เสาประตูซ้าย: "THE END OF ALL GOOD GOVERNMENT IS THE HAPPINESS OF THE PEOPLE" เสาประตูขวา: "THE FOUNDATION OF EVERY STATE IS ITS EDUCATION OF ITS YOUTH" บังเอิญเหลือเกินที่พกหนังสือ "หลังโครงสร้างนิยม: ฉบับย่อ" เขียนโดยแคทเธอรีน เบลซีย์ แปลโดยอภิญญา เฟื่องฟูสกุล ติดมือไปด้วย แล้วก็บังเอิญเช่นกันที่อ่านเจอข้อความนี้: "[...] ประเด็นหลักของอัลตูแซร์ก็คือโรงเรียนและมหาวิทยาลัยไม่เพียงผลิตคนหนุ่มสาวป้อนตลาดแรงงานทุกระดับของโครงสร้างเศรษฐกิจเท่านั้น ทว่าในกระบวนการสอนอ่านเขียนและคิดเลข ก็ผลิตคำสอนเรื่องความเชื่อฟัง ความสุภาพอ่อนน้อม จิตวิทยาเบื้องต้น [...] คุณค่าของประชาธิปไตยเสรีนิยม วิธีออกคำสั่ง และวิธีทำงานรับใช้ชุมชน กล่าวสั้น ๆ ก็คือ สถาบันการศึกษาทำให้วินัย โดยเฉพาะวินัยในตัวเองหยั่งรากฝังลึกในความคิดและสนับสนุนให้นักเรียนออกไปสู่สังคมและผดุงรักษาสภ...
Read more

กฎแห่งการมีจำนวนมาก (1)

(ในบล็อก wonam.exteen.com ผมมักจะเขียนเรื่องทั่ว ๆ ไป แต่สำหรับบล็อกนี้ ผมจะพยายามเีขียนเรื่องที่เกี่ยวข้องกับวิทยาการคอมพิวเตอร์เชิงทฤษฎี ซึ่งอาจเป็นเรื่องที่ผมศึกษาอยู่ หรือไปผ่าน ๆ ตามา) ให้เหรียญที่เที่ยงตรงมาหนึ่งอัน โยน 2 ครั้ง แล้วนับจำนวนหัวที่ออกมา ตามหลักความน่าจะเป็น ค่าคาดหวัง (expected value) ของจำนวนหัวก็คือ 1 แต่อย่างไรก็ตาม ไม่จำเป็นที่ผลที่ได้เป็นเช่นค่าคาดหวังเสมอไป ถ้าลองคำนวณดูจะพบว่า ความน่าจะเป็นที่จะได้หัว 1 ครั้งพอดี มีค่าเท่ากับ 0.5 เท่านั้น แล้วความน่าจะเป็นที่เราคำนวณมาเนี่ยะ มันจะมีประโยชน์อะไร? เช่นถ้าเราบอกว่าเหตุการณ์หนึ่งจะเกิดขึ้นด้วยความน่าจะเป็น 0.5 จริง ๆ แล้วมีความหมายอะไรหรือไม่? ถ้าถกกันเรื่องความหมายแล้ว จริง ๆ ก็ตอบได้ยาก แต่ถ้าเรายึดโมเดลมาตรฐานทั่วไปของความน่าจะเป็น เราสามารถแสดง "ความหมาย" ของตัวเลขความน่าจะเป็นพอได้บ้าง ความเข้าใจหนึ่งที่เรามีเกี่ยวกับความน่าจะเป็นก็คือจำนวนครั้ง โดยเฉลี่ย ที่เหตุการณ์หนึ่ง ๆ จะเกิดขึ้น แน่นอนคำว่าโดยเฉลี่ยนั้น มีนัยยะของจำนวนอยู่ด้วย นั่นคือ ยิ่งมีการทดลองมากครั้งเข้า จำนวนครั้งของการเกิดขึ้น...
Read more