พูดคุย:เอ็นพี (ความซับซ้อน)

อาจจะไม่ตรงตามจุดประสงค์ของหน้าพูดคุยซะทีเดียวนะครับ อย่างไรก็ตามขอใช้เนื้อที่ตรงนี้ ถามคำถามที่เกี่ยวกับบทความนี้ซะหน่อย:

ทำไมกลุ่มปัญหาใน NP-Hard และ co-NP ถึงได้รับความสนใจน้อยกว่า NP-complete ล่ะครับ ? นิยาม completeness ที่ให้ไว้ เกี่ยวกับเรื่องสับเซต มีอะไรเป็นพิเศษในการแก้ปัญหาเหรอครับ ?

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

จากปัญหา PRIME ทำให้เราทราบได้ว่า กลุ่ม co-NP และ NP มีส่วนที่ intersect กันใช่ไหมครับ ?

ขออภัย ครูบาอาจารย์ที่เคยสั่งสอนมา เนื่องจากยังไม่สามารถทบทวนบทเรียนได้ในตอนนี้ครับ ^___^' -- จุง 05:20, 19 ธันวาคม 2005 (UTC)

ข้อแนะนำ: ในประโยค

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

น่าจะมีการพูดถึงกลุ่ม อัลกอริทึมเชิงสุ่ม (randomized algorithms) กับ อัลกอริทึมเชิงประมาณ (approximation algorithms) ซักหน่อยหรือเปล่าครับ? -- จุง 05:23, 19 ธันวาคม 2005 (UTC)

1. co-NP และ NP intersect กันแน่นอนที่ P แต่ไม่มีใครทราบว่ามีปัญหาที่อยู่ใน NP แต่ไม่อยู่ใน co-NP หรือไม่ แต่เราทราบว่า ถ้า P=NP แล้ว NP=co-NP, แต่ในทิศทางกลับกันยังเป็นปัญหาเปิดอยู่ (ดู [1])

2. การหาอัลกอริทึมที่แก้ปัญหาใน co-NP หรือ NP ได้ ไม่ได้แปลว่าจะแก้ปัญหาอื่น ๆ ใน NP ได้ทั้งหมด ยกเว้นเราจะสามารถแก้ปัญหาที่เป็น NP-complete ได้ นั่นก็คือปัญหาที่ยากที่สุดใน NP ผมว่าด้วยสาเหตุนี้จึงทำให้ปัญหาในเซต NP-complete สำคัญมาก (มากกว่า co-NP)

3. ปัญหาที่เป็น NP-hard นั้น โดยทั่วไปที่เป็นปัญหา optimization, ส่วนมากก็จะมี decision version ที่เป็น NP-complete ยกเว้นปัญหาที่ยากกว่ามาก ๆ ทีนี้ คนที่สนใจ optimization problem มักมุ่งไปที่ approximation algorithm มากกว่า (และมักเชื่อว่า P!=NP)

หาไม่เจอตรงที่พูดเกี่ยวกับสับเซตน่ะ ส่วนการพูดถึง approx alg. ในพารากราฟข้างต้น เดี๋ยวจะลองเอาไปใส่ให้ครับ --- Jittat 05:50, 19 ธันวาคม 2005 (UTC)

เข้ามาสงสัยด้วยคนครับ คือยังสับสนว่าทำไม NP ถึงไม่เท่ากับ Co-NP เหรอครับ

-> คือสมมุติเรามีปัญหา ${\mathcal {X}}$ ที่อยู่ใน NP ซึ่งมีอัลกอรึทึม A ที่สามารถ verify ว่า x เป็นคำตอบของ ${\mathcal {X}}$ รึเปล่า ได้ในเวลาที่เป็น polynomial

-> แล้ว complement ของ ${\mathcal {X}}$ ก็น่าจะใช้อัลกอริทึม A มา verify ได้

-> จากนั้นก็กลับคำตอบ จาก yes เป็น no จาก no เป็น yes

-> เพราะฉะนั้น complement ของ ${\mathcal {X}}$ ก็อยู่ใน NP

-> จึงได้ว่า ${\mathcal {X}}$ อยู่ใน Co-NP ด้วย ???

พอดีผมไม่ได้ศึกษามาด้านนี้น่ะครับ อาจจะเข้าใจผิดไปมากเลยก็ได้ ยังไงวานท่านผู้รู้ไขข้อข้องใจหน่อยครับ :)

ขอโทษทีครับ ตรงส่วนนี้ (การ verify คำตอบของเอ็นพี) ผมเขียนยังไม่ค่อยชัดเจนเท่าไรนักด้วย (เนื่องจากว่าใน web ของภาษาอังกฤษก็เขียนไม่ดีนัก) อีกไม่นานจะไปแก้ไขให้ชัีดเจนขึ้นครับ คิดว่าคงจะเข้าไปแก้เร็วๆนี้เลยล่ะครับ อีกวันสองวันลองเข้าไปเช็คใน เอ็นพี (ความซับซ้อน) ได้ครับ แต่ถ้าจะอธิบายตรงนี้เลยคร่าวๆก็คือ คำว่า verify นั้นคือการที่ "มีบทพิสูจน์ให้ verify" ถ้าลองมองนิยามแบบนี้ นิยามของเอ็นพีก็คือ

• ปัญหา A เป็นเอ็นพีเมื่อมีเครื่องจักรทัวริง V ที่มีสมบัติคือ
  • ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ใช่" เราสามารถหาบทพิสูจน์ที่ V ยอมรับได้
  • ถ้า x เป็นตัวอย่างของปัญหาที่ตอบว่า "ไม่ใช่" จะไม่มีบทพิสูจน์ใดที่ V ยอมรับ

เพราะฉะนั้นวิธีการของคุณ ที่บอกว่าให้ใช้ V ตัวเดียวกันมา Verify แล้วกลับคำตอบจะมีปัญหาคือ กรณีที่ x เป็นตัวอย่างปัญหาที่ตอบ "ไม่ใช่" บทพิสูจน์บางอย่างอาจจะถูกยอมรับไปด้วย ซึ่งขัดกับนิยามของ NP ครับ --Ed 06:26, 21 ธันวาคม 2005 (UTC)

ขอบคุณ Ed Jittat และ จุง เป็นอย่างสูงครับ สิบปีผ่านไปพอมาอ่านใหม่แล้วเพิ่งจะเข้าใจ :P -- อั๋น (พูดคุย) 22:45, 13 พฤษภาคม 2558 (ICT)

เกี่ยวกับนิยามความบริบูรณ์

อืม เกี่ยวกับเรื่องสับเซ็ต ไม่แน่ใจว่าตอบตรงคำถามรึเปล่านะ แต่ว่าในหน้าของ ทฤษฏีความซับซ้อนในการคำนวณ ได้นิยามความบริบูรณ์ไว้ว่า X บริบูรณ์สำหรับ Y เมื่อ

• Y ลดรูปไปเป็น X (X ยากสำหรับ Y)
• X เป็นสับเซตของ Y

อืม นิยามแบบนี้ไม่มีอะไรพิเศษในการแก้ปัญหาหรอกอะ แต่นี่เป็นการนิยามแบบที่ค่อนข้าง general มาก สามารถนำไปใช้ินิยามความบริบูรณ์ของเซ็ตอะไรก็ได้ ขออธิบายความหมายของคำว่า "บริบูรณ์" ซักนิด แต่ก่อนอื่นขออธิบายคำว่า "ยาก" ก่อน

ปัญหา "ยาก" ของ เซ็ต X หมายความว่าถ้าแก้ปัญหานั้นแล้วจะแก้ปัญหาืทั้งหมดของเซ็ตนั้นได้ แต่ปัญหาที่ยากสำหรับเ็ซ็ต X ไม่จำเป็นต้องเป็นป้ัญหาในเซ็ต X

ตัวอย่างเช่น

• ปัญหาการนับจำนวนของ satisfying assignment ใน SAT: ปัญหานี้เป็น เอ็นพีแบบยาก เพราะว่าถ้าเรานับได้ว่าจำนวน satisfying assignment เป็นเท่าไร เราก็สามารถตอบคำถามได้ว่า "มี satisfying assignment หรือไม่"
• ปัญหาการ "หา" satisfying assigment ใน SAT: เป็น เอ็นพีแบบยากเช่นกัน

แต่ทั้งสองปัญหานี้ไม่ใช่เอ็นพี (เพราะว่าไม่ใช่ปัญหาการตัดสินใจ)

เพราะฉะนั้น คำว่า "ยาก สำหรับ X" สื่อไปถึงว่าปัญหานั้นยากกว่าทุกปัญหาในเซ็ต X แต่ไม่ได้สื่อว่าปัญหานั้นอยู่ใน X หรือเปล่า

ในทางกลับกัน "ความบริบูรณ์" จะสื่อว่าเป็นปัญหาที่ยาก และอยู่ภายในเซ็ตนั้นด้วย จึงต้องการนิยามในส่วน "X เป็นสับเซ็ตของ Y" ด้วย มากไปกว่านั้น ความบริบูรณ์ยังสื่อว่า ถ้าปัญหาที่เป็น "บริบูรณ์" ง่าย จะส่งผลให้ทุกปัญหาในเซ็ตง่ายไปด้วย เหมือนกับว่าความเป็นบริบูรณ์บ่งบอกถึงความเป็นตัวแทนความยากของกลุ่มนั้น (ดูตัวอย่างข้างล่าง)

ทำไมนิยามแบบนี้

อย่างที่บอกไปแล้วว่านิยามแบบนี้ general มากขนาดที่ว่าจะนำไปนิยามความบริบูรณ์ของอะไรก็ได้ เช่น (ให้สังเกตุว่านิยามความบริบูรณ์ทุกอย่างจะมี notion ของ "ความง่าย" ปนเข้ามา ซึ่งจะเปลี่ยนไปตามปัญหาที่สนใจ ซึ่ง reduction ต้องง่าย )

• EXP-complete: ปัญหาที่แก้ได้ใน exponential time และสามารถทำ poly-time reduction ได้จากทุุกปัญหาใน EXP (ถ้าแก้ EXP-complete ได้ใน polytime จะส่งผลให้ P=EXP) ความง่าย= poly-time

• NL-complete: เป็นปัญหาที่อยู่ใน NL และสามารถทำ log-space reduction ได้จากทุึกปัญหาใน L (ถ้าแก้ NL-complete ได้ใน log-space จะส่งผลให้ L=NL) ในที่นี้ความง่าย แทนด้วย log-space

• P-complete: เป็นปัญหาที่อยู่ใน P และสามารถทำ log-space reduction ได้จากทุกปัญหาใน P (ถ้าแก้ P-complete ได้ใน log-space จะส่งผลให้ L=P) ในที่นี้ความง่ายแทนด้วย log-space

• NP-complete: ความง่าย= poly-time
• #P-complete: ความง่าย= poly-time

มีตัวอย่างอีกเยอะ ....

อืม พอเข้าใจป่าวอะ

โอ้ กระจ่างขึ้นมาเยอะเลยครับ ขอบคุณทั้งสองคน มากๆๆ :) แต่ยังสงสัยอีกนิดหน่อยว่า ในงานวิจัยปัจจุบัน นักวิจัยสนใจที่จะแก้ปัญหา NP-complete ให้ได้อย่างมีประสิทธิภาพ (ซึ่งทำให้ได้ว่า P=NP) แล้วในงานวิจัยปัจจุบัน เขาสนใจที่จะหาอัลกอริทึมที่มีประสิทธิภาพที่จะแก้กลุ่มปัญหาบริบูรณ์ใน class อื่นๆ เช่น #P-complete, co-NP complete, NL-complete บ้างหรือเปล่า ? (หมายถึงว่า ฮิตทำวิจัยกันพอ ๆ กับทำปัญหาใน NP-complete หรือเปล่า?) ที่ถามก็เพราะอยากรู้ว่าความรู้ที่มีล้าหลังมากไปกี่ปี (ไม่น่าจะต่ำกว่า 45 ปี) -- จุง 15:41, 20 ธันวาคม 2005 (UTC)

อืมในปัจจุบันปัญหา complete ของคลาสหลายๆคลาสก็เป็นที่สนใจของนักวิจัยเช่นกัน เช่น ล่าสุด Omer Reingold (ปีที่แล้ว) พิสูจน์ว่า SL-complete แก้ได้ใน log-space ส่งผลให้ L=SL ซึ่งก่อนหน้านี้เรารู้แค่ว่า $L\subseteq SL\subseteq RL\subseteq NL$ ตอนนี้ Reingold กำลังทำ L=RL อยู่ .... แล้วก็ประมาณปี 1989 มั้ง Immerman พิสูจน์ว่า coNL-complete แก้ได้ใน NL ส่งผลให้ NL=coNL ....

• #P-complete เป็นปัญหาของการนับ เช่น หาค่า permanent ของ matrix, นับจำนวน cycle cover บนกราฟ, นับ satisfying assignement, นับจำนวน matching ในกราฟ, etc. ไม่ค่อยมีใครพยายามนับกันอย่างมีประสิทธิภาพหรอก เพราะมันยากกว่า NP-complete อีก (อย่างน้อยถ้านับได้ใน poly-time จะเป็นการพิสูจน์ว่า P=NP) งานวิจัยเลยไปสนใจที่การทำ approximate counting แทน อาจจะเห็นได้จากว่ามิงานวิจัยที่เกี่ยวกับ approximate permanent ของ matrix ออกมาเต็มไปหมด ซึ่งบางคนอาจจะสงสัยว่าทำไปเพื่ออะไร แต่จริงๆแล้วมันสำคัญมากเพราะถ้านับ permanent ได้ ก็นับจำนวน solutions ของปัญหา NP ได้ทุกปัญหา ... ปัญหา#P ยากถึงขนาดที่ถ้านำไปใช้เป็น oracle จะสามารถแก้ปัญหาทั้งหมดใน PH (polynomial hierarchy) ได้ ซึ่ง NP-complete ที่เราเชื่อกันว่ายาก อยู่แค่ชั่นที่ 1 ของ PH เท่านั้น $PH\subseteq P^{\#P}$ (Toda's theorem)

• ส่วน coNP-complete ถ้าแก้ได้ใน NP ก็คงดี (หรือพูดอีกแบบว่า NP is closed under complement) แต่คนก็เชื่อกันว่าทำไม่ได้อะ ความเชื่อตรงนี้เชื่อมโยงไปถึงความเชื่อเกี่ยวกับ polynomial hierarchy (PH) เพราะว่าถ้า $coNP\subseteq NP$ จะส่งผลให้ PH collapse (ซึ่งคนส่วนใหญ่เชื่อกันว่า PH ไม่ collapse) ส่วนคนที่พยายามพิสูจน์ว่า coNP != NP ก็ไม่น่าจะมีเช่นกัน เพราะมันจะส่งผลให้ P!=NP เพราะฉะนั้นความยากน่าจะพอๆกับพิสูจน์ว่า P!=NP

• ความรู้ที่เราเรียนกันในชั้นเรียน (ปริญญาตรี) ทั้งหมดเป็นผลงานก่อนปี 1975: Cook พิสูจน์ NP-complete ปี 71, Karp พิสูจน์ีอีก 23 ปัญหาในปี 72 และที่เราเรียนกันทั้งหมดก็อยู่ในงานสองชิ้นนี้แหละ :)

--Ed 18:10, 20 ธันวาคม 2005 (UTC)

---

น่า จะ มี ลิงก์ อ้างอิง การ ยืนยัน ว่า prime เป็น P, เพราะ ผม ก็ อยาก รู้ เหมือนกัน ว่า ทำ ยังไง :b แล้ว ทำไม prime ถึง เป็น co-NP นี้ ก็ อ่าน ไม่ เข้าใจ แหะ. --Ans 10:12, 29 พฤษภาคม 2006 (UTC)