ผลต่างระหว่างรุ่นของ "204512-53/lecture13"
ไปยังการนำทาง
ไปยังการค้นหา
G521455033 (คุย | มีส่วนร่วม) |
G521455033 (คุย | มีส่วนร่วม) |
||
| แถว 11: | แถว 11: | ||
Proof: ให้ <math>\varnothing</math> เป็น 3-CNF ใดๆ <br> | Proof: ให้ <math>\varnothing</math> เป็น 3-CNF ใดๆ <br> | ||
<math>(x_1\or\lnot x_2\or \lnot x_3 ) \and (\lnot x_1 \or \lnot x_3 \or x_4 ) \and (x_5 \or x_6 \or \lnot x_4)</math> | <math>(x_1\or\lnot x_2\or \lnot x_3 ) \and (\lnot x_1 \or \lnot x_3 \or x_4 ) \and (x_5 \or x_6 \or \lnot x_4)</math> | ||
| − | และ m clause เรียกเป็น <math>C_1,C_2,C_2,...,C_M</math> | + | และ m clause เรียกเป็น <math>C_1,C_2,C_2,...,C_M</math> จะสร้างกราฟได้ดังนี้ |
| + | **ในแต่ละ clause <math>C_i</math> สร้างสามเหลี่ยมที่ประกอบไปด้วยโหนดตัวแปรที่ปรากฎใน C ได้กราฟที่มี 3 โหนด ตามรูป | ||
| + | สำหรับทุกตัวแปร <math>X_i</math> เชื่อมทุกโหนดที่แทนตัวแปร <math>X_j</math>กับทุกโหนดที่แทน <math>\lnot X_j</math> | ||
รุ่นแก้ไขเมื่อ 05:36, 7 ตุลาคม 2553
จดบันทึกคำบรรยายโดย:
นายเสกสิทธิ์ สุวรรณ รหัสนักศึกษา 5214550332
NP Complete
ปัญหา A P (Polynomail time to) ปัญหา B ถ้า มี poly-time algo ที่สำหรับทุกๆ instance x ของ A
x' = T(x) , | x' | = poly (| x |)
และถ้า x เป็น yes instance ของ A , x' เป็น yes-instance ของ B
x เป็น no instance ของ A , เป็น no-instance ของ B
THM: 3-SAT p INDEP-SET
Proof: ให้ เป็น 3-CNF ใดๆ
และ m clause เรียกเป็น จะสร้างกราฟได้ดังนี้
- ในแต่ละ clause สร้างสามเหลี่ยมที่ประกอบไปด้วยโหนดตัวแปรที่ปรากฎใน C ได้กราฟที่มี 3 โหนด ตามรูป
สำหรับทุกตัวแปร เชื่อมทุกโหนดที่แทนตัวแปร กับทุกโหนดที่แทน
