Arxiv hàng ngày

Đây là trang tổng hợp các bài báo về trí tuệ nhân tạo được xuất bản trên toàn thế giới.
Trang này sử dụng Google Gemini để tóm tắt nội dung và hoạt động phi lợi nhuận.
Bản quyền của các bài báo thuộc về tác giả và tổ chức liên quan; khi chia sẻ, chỉ cần ghi rõ nguồn.

ĐếM SMT gần đúng ngoài miền rời rạc

Created by
  • Haebom

Tác giả

Arijit Shaw, Kuldeep S. Meel

Phác thảo

Bài báo này trình bày một bộ đếm mô hình SMT mới, được gọi là pact, để giải quyết bài toán đếm mô hình cho công thức SMT (Lý thuyết Môđun Khả Năng Đáp Ứng) lai. Trong khi các phương pháp tiếp cận dựa trên bit-blasting hiện có hạn chế là bị giới hạn ở các biến rời rạc, pact ước tính số lượng nghiệm với các đảm bảo lý thuyết bằng cách sử dụng phép đếm mô hình xấp xỉ dựa trên hàm băm. pact thực hiện các lệnh gọi trình giải SMT logarit cho các biến chiếu và cải thiện hiệu suất bằng cách sử dụng các hàm băm được tối ưu hóa. Các thử nghiệm chuẩn mở rộng cho thấy pact cải thiện đáng kể hiệu suất so với các phương pháp hiện có. Ví dụ, trong số 14.202 trường hợp, pact xử lý thành công 603 trường hợp, trong khi các phương pháp hiện có chỉ xử lý được 13.

Takeaways, Limitations

Takeaways:
Một kỹ thuật đếm mô hình gần đúng hiệu quả cho công thức SMT lai được trình bày.
Các phương pháp dựa trên băm có thể giải quyết được nhiều vấn đề hơn so với các phương pháp truyền thống.
Cung cấp kết quả đếm mô hình gần đúng với các đảm bảo về mặt lý thuyết.
Xác nhận hiệu suất vượt trội thông qua các thử nghiệm chuẩn mực quy mô lớn.
Limitations:
Vì đây là mô hình đếm gần đúng nên không đảm bảo số lượng giải pháp chính xác.
Nhiều trường hợp vẫn chưa được giải quyết (hơn 13.600/14.202). Tỷ lệ thành công vẫn còn thấp.
👍