Analysis of algorithm Chapter 12 : NP-complete

ข้อความใดจริงเกี่ยวกับ Decision Problem (อาจมีหลายคำตอบ ตอบให้ครบ)

• ให้ผลลัพธ์เป็น true หรือ false เท่านั้น

• สามารถนำไปใช้ในการแก้ปัญหา Optimization problem ที่แปลงมาได้

• "ยาก"กว่า Optimization problem ที่แปลงมาเสมอ

• ใช้ในการพิจารณาชนิดของปัญหา (P vs NP)

• การหาจำนวนสีที่ใช้ใน graph coloring เป็น decision problem

ข้อใดจริงเกี่ยวกับปัญหา NP (อาจมีหลายคำตอบ ตอบให้ครบ)

• ปัญหา NP สามารถตรวจสอบคำตอบว่าเป็น "Yes" หรือไม่ได้ใน polynomial time

• ปัญหา NP สามารถหาผลเฉลย non-deterministic machine ได้ใน polynomial time

• ปัญหา NP คือปัญหาที่ใช้เวลาหาคำตอบ ไม่เป็น polynomial (Non-polynomial)

• ทุกปัญหา P เป็นปัญหา NP

• Co-NP คือปัญหาที่ไม่ใช่ปัญหา NP

ข้อใดคือความหมายของ Non-deterministic machine

• มีขั้นตอนการเดาคำตอบใน polynomial time

• มีเวลาในการหาคำตอบเป็น Exponential

• มีเวลาในการทดสอบคำตอบว่าถูกต้องหรือไม่ไม่แน่นอน

• เป็นเครื่องมือในการแก้ปัญหาที่มีระดับความยากสูงสุด

• ปัญหาที่มีระดับความยากสูงสุด

  สามารถหาผลเฉลยได้โดยไม่ต้องใช้เครื่องจักร

ข้อใดไม่จริงเกี่ยวกับ NP-Complete และ NP-Hard

• ทุกปัญหา NP-Hard เป็นปัญหา NP

• ทุกปัญหา NP-Complete เป็นปัญหา NP

• ถ้าปัญหา X สามารถลดรูปเป็นปัญหา SAT ได้ จะได้ว่า ปัญหา SAT เป็นปัญหา NP-Complete

• SAT สามารถลดรูปเป็นปัญหา NP-Hard ได้

ข้อใดเป็นแผนภาพแสดงการแบ่งประเภทของปัญหาได้ถูกต้อง

• 
• 
• 
• 

ข้อใดไม่จริง ถ้า ปัญหา X ลดรูปได้เป็น Y

• ถ้าปัญหา X เป็นปัญหา NP สรุปได้ว่า ปัญหา Y ต้องเป็นปัญหา NP

• ปัญหา X ไม่ยากกว่า Y

• ถ้าปัญหา Y ลดรูปได้เป็น Z และปัญหา Z ลดรูปได้เป็น X จะได้ว่า X, Y, Z มีความยากเท่ากัน

• สามารถใช้ขั้นตอนการแก้ปัญหาของ X แก้ปัญหาของ Y ได้

ข้อใดจริงเกี่ยวกับปัญหา 3-SAT

• สามารถหาผลเฉลยได้ด้วย polynomial time

• สามารถตรวจผลเฉลยได้ด้วย polynomial time

• ทุกปัญหาที่เป็น NP-Complete สามารถลดรูปได้เป็นปัญหานี้

ปัญหาใดเป็นปัญหา P

• ปัญหาการเรียงลำดับ

• ปัญหา N-Queen

• ปัญหา Knapsack

• ปัญหา Palindrome