ข้อสอบเก่า 204512 บางส่วน

ปัญหาห้องเก็บของ

มีห้องเก็บของ $k$ ห้อง (เมื่อ $k\geq 3$) ต้องการนำของ $n$ ชิ้นไปเก็บในห้อง อย่างไรก็ตาม มีเงื่อนไขว่าของบางชิ้นไม่สามารถเก็บในห้องเดียวกันได้ กล่าวอย่างเป็นทางการก็คือ มีเซต $A$ ของคู่ลำดับ ที่ถ้าคู่ลำดับ $(i,j)\in A$ ของชิ้นที่ $i$ กับของชิ้นที่ $j$ จะไม่สามารถเก็บในห้องเดียวกันได้

สำหรับปัญหานี้ เราอยากทราบว่าสามารถเก็บของทุกชิ้นไว้ในห้องโดยไม่ผิดเงื่อนไขได้หรือไม่?

จงแสดงว่าปัญหาดังกล่าวเป็นปัญหา NP-Complete อธิบายด้วยว่าทำไมการลดรูป (reduction) ที่ใช้ถึงถูกต้อง

Hint: อาจลดรูปปัญหา 3-COLOR ไปยังปัญหาห้องเก็บของ