CÁC KỸ THUẬT SAT SOLVING

Abstract

SAT Solving là bài toán chứng minh sự thỏa mãn (SAT / UNSAT) của một công thức Lôgic mệnh đề (Propositional Lôgic) và các công cụ tự động SAT Solver đóng vai trò là các bộ giải công thức đó. Ngày nay các SAT Solver cũng đóng vai trò là các công cụ nền cho các SMT (SAT Module Theories) Solver, những công cụ tự động chứng minh sự thỏa mãn hay không thỏa mãn (SAT/UNSAT) của các công thức lôgic trên lý thuyết vị từ cấp I (FOL I). Các nghiên cứu về SMT Solver hiện nay đang là các chủ đề có tính thời sự, bởi SMT Solver được ứng dụng trong các bài toán về kiểm chứng, kiểm thử chương trình. Bài toán SAT là bài toán có độ phức NP và các kỹ thuật SAT Solving đã được nghiên cứu, phát triển đã lâu. Tuy nhiên, sự phát triển mạnh mẽ của các SAT solver trong những năm gần đây thông qua các cuộc thi SAT Competition tổ chức hàng năm cho thấy nhiều kỹ thuật cải tiến trong cài đặt các SAT solver đã được tiến hành thực nghiêm. Ngày nay các SAT solver có khả năng giải quyết các công thức lên đến hàng triệu biến với hàng trăm ngàn mệnh đề. Luận văn đi sâu tìm hiểu các kỹ thuật cơ bản, các thuật toán cơ bản được cài đặt trong các SAT solver, đồng thời đưa ra các ví dụ minh họa cụ thể nhằm làm rõ cách thức hoạt động. Các kỹ thuật này được cài đặt trong một SAT solver phổ biến hiện nay đó là MiniSAT, một SAT solver mã nguồn mở mà rất nhiều SAT solver mạnh trên thế giới được mở rộng cải tiến từ SAT Solver này. Bên cạnh đó, luận văn cũng tìm hiểu 2 kĩ thuật tiên tiến đang được cài đặt trong các SAT Solver mạnh hiện nay là GlueMinisat, Glucose. Luận văn tiến hành chạy thực nghiệm so sánh 3 SAT solver này trên các bộ dữ liệu thực nghiệm chuẩn (từ cuộc thi SAT competition) để thấy rõ tính hiệu quả, tính nhanh nhạy của các kỹ thuật tiên tiến đang được sử dụng.