Ai rành về thuật toán (bài toán 3-SAT và 3-DM) vào giúp mình với

[killeroflove1989]

Mình đang cần chứng minh hai bài toán 3-SAT và 3-DM(3 dimension matching tiếng việt đối sánh 3 chiều ) thuộc lớp bài toán NPC. Nhưng hiện tại mình vẫn chưa hiểu rõ nội dung của hai bài toán này lắm, tìm tài liệu thì toàn ENG rất khó hiểu, ai biết yêu cầu và giả thiết của 2 bài toán này thì giúp mình với , tiện thể có phương pháp chứng minh thì post hộ mình luôn, thanks :)

 

[Xenogear]

SAT đã được chứng mình là trong NPC nên map 3-SAT vào SAT là được
để chứng minh là SAT và 3-SAT khó ngang nhau thì cần chứng mình là bất cứ một biểu thức SAT nào cũng có thể viết lại bằng 3-SAT mà không thay đổi truth value
tham khảo thêm bài này, thực ra học cái này mà ngại đọc tiếng anh thì chịu, chả biết phải giúp kiểu gì
http://www.soe.ucsc.edu/classes/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf