ข้อสอบเก่า 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

คุณหมอ

คุณหมอมียาปฏิชีวนะ $M$ แบบ ให้เซต ${\mathcal M}=\{1,2,\ldots,M\}$ แทนเซตของยาเหล่านี้

 คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น $N$ ชนิด เชื้อโรคที่ $i$ สำหรับ
 $1\leq i\leq N$ สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต $A_i\subseteq
 {\mathcal M}$ ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต $A_i$ เชื้อโรคที่ $i$
 ก็จะตาย)

 คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง $k$ ชนิด
 เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่

• เรียกปัญหาดังกล่าวว่าปัญหา {\sc MinMed} จงแสดงว่าปัญหา {\sc MinMed} เป็นปัญหาในกลุ่ม NP

• จงแสดงว่าปัญหา {\sc MinMed} เป็นปัญหา NP-complete โดยการลดรูปจากบางปัญหา NP-complete ไปยัง {\sc MinMed}

คำใบ้: พิจารณาปัญหา {\sc VertexCover} ที่อธิบายได้ดังนี้ ให้กราฟ

   $G=(V,E)$ และจำนวนเต็ม $k$ หาว่ามีเซต $C\subseteq V$ ที่ $|C|=k$ และทุก
   ๆ เส้นเชื่อม $e\in E$ มีจุดปลายอย่างน้อยหนึ่งจุดอยู่ใน $C$