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

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

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

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

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

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

รหัสพันธุกรรม

ในการศึกษาเกี่ยวกับรหัสพันธุกรรมนั้น เรามักจะพิจารณาสายรหัสพันธุกรรมเป็นสตริงของตัวอักษร {A,G,T,C} โดยในปัญหานี้เราจะสนใจสตริงความยาว m เท่านั้น ในการวิเคราะห์กลุ่มของสิ่งมีชีวิต เรามักจะได้สตริงเหล่านี้มาเป็นจำนวนมาก อย่างไรก็ตามเนื่องจากค่าใช้จ่ายและเวลาในการวิเคราะห์รหัสพันธุกรรมสายหนึ่งนั้น ค่อนข้างสูง เราจึงต้องการจะลดจำนวนสตริงที่จะวิเคราะห์โดยละเอียดลง โดยสตริงที่คล้าย ๆ กัน เราจะเลือกตัวแทนมาแค่สตริงเดียว ในการวัดว่าสตริงคู่ใดคล้ายกันหรือไม่ เราจะพิจารณาจากจำนวนตำแหน่งที่มีตัวออักษรเหมือนกันในสองสตริงนั้น ยกตัวอย่างเช่นสตริง AGAAG กับสตริง ATATG มี 3 ตำแหน่งที่เหมือนกัน ถ้าจำนวนของตำแหน่งนี้มากกว่าหรือเท่ากับ k เราจะนับว่าสตริงคู่นั้น “คล้ายกันระดับ k ”

ปัญหาที่เราต้องการแก้คือ: ให้เซต S ของสตริง n สตริง ที่มีความยาว m และค่าคงที่ k และ l , มีเซตของสตริง ที่มีจำนวน l สตริง และทุก ๆ สตริง s ใน S มีสตริง x ใน T ที่คล้ายกันระดับ k กับ s หรือไม่?

เราจะเรียกปัญหานี้ว่า “ปัญหาตัวแทนสตริง” จงแสดงว่าปัญหานี้เป็นปัญหา NP-Complete