Mr Gate
31-08-2009, 05:40 PM
Từ các công trình của Mitchell, Selman và Levesque năm 1992, người ta đã nhận thấy rằng một số bài toán tính số có thể được giải quyết bằng các tìm hiểu và khai thác thông tin từ các pha chuyển tiếp (phase transistions) tại các giá trị đặc biệt của tham số, ví dụ như tại nhiệt độ 0 tuyệt đối. Bài toán 3-SAT ,phát triển từ công thức Boolean ở đó phát biểu rằng, từ các mệnh AND, OR, NOT, liệu có khả năng nào mà biểu thức chứa 2 mệnh đề TRUE và FALSE lại cho kết quả là hoàn toàn TRUE hay không. Bài báo với tựa đề "Analytic and Algorithmic Solution of Random Satisfiability Problems" (Science , August 2 2002) của Marc Mézard, Giorgio Parisi và Riccardo Zecchina (Orsay) đã sử dụng thống kê cổ điển để nghiên cứu pha chuyển tiếp, và chuyển về bài toán lý thuyết thuần túy: tìm xác suất để một tập k-SAT có ít nhất một phần tử thỏa mãn điều kiện SAT. Từ SAT xuất phát từ chữ cái đầu của SATisfiability, hay còn gọi là bài toán Boolean satisfiability.
Từ kết quả của Marc Mézard và Marco Tarzia, Statistical mechanics of the hitting set problem xuất hiện (Phys Rev E76 041124) năm ngoài, nhà toán học Bart Selman đã phát biểu trên mục "Tin tức và thời sự " của tạp chí Nature tháng 2, rằng các tác giả của bài báo trên đã sử dụng thống kê cổ điển như một hướng tiếp cận với bài toán NP-hoàn chỉnh nổi tiếng, được gọi với cái tên hitting-set problem. (HSP). Một tập con hitting được chọn từ Hợp (union) của các tập hợp ở đó chưa ít nhận một phần tử, bài toán tương đương với việc tìm một tập hitting với số lượng các phần tử là nhỏ nhất. Mézard và Tarzia nhận thấy rằng "các công cụ trong vật lý thống kê đã được phát triển để nghiên cứu các pha vật lý chuyển tiếp có thể giúp trong việc xây dựng các thuật toán hiệu quả để giải các bài toán tổ hợp", thu thập từ các bước tính về các tính chất ở mức năng lượng cơ bản của các hệ vật lý chất rắn, dẫn đến phương pháp truyền -thăm dò (survey-propagation method). "Mézard và Tarzia sử dụng phương pháp này để tìm hiểu các tính chất thống kê trong các nghiệm của một số trường hợp cá biệt ở bài toán HSP. Điều này còn khó hơn cả so với việc tìm một nghiệm cụ thể, nhưng phương pháp truyền -thăm dò trên biên của một pha, có thể thu thập được các thông tin cần thiết." bằng thuật toán hồi quy của một tập hợp lớn các phương trình cặp, mô hình các tương tác địa phương giữa các biến một cách xác suất. Quá trình tìm nghiệm này có thể được thực hiện bằng phương pháp tính song song, do vậy có thể nhận được kết quả từ nhiều nhà toán học khác, nghiệm sẽ hội tụ sớm hớn trong một thời gian tính tương đối ngắn - chỉ vài giây cho các phương trình với hàng ngàn biến."
Nguồn: Hội Toán Học Mỹ (AMS)
Từ kết quả của Marc Mézard và Marco Tarzia, Statistical mechanics of the hitting set problem xuất hiện (Phys Rev E76 041124) năm ngoài, nhà toán học Bart Selman đã phát biểu trên mục "Tin tức và thời sự " của tạp chí Nature tháng 2, rằng các tác giả của bài báo trên đã sử dụng thống kê cổ điển như một hướng tiếp cận với bài toán NP-hoàn chỉnh nổi tiếng, được gọi với cái tên hitting-set problem. (HSP). Một tập con hitting được chọn từ Hợp (union) của các tập hợp ở đó chưa ít nhận một phần tử, bài toán tương đương với việc tìm một tập hitting với số lượng các phần tử là nhỏ nhất. Mézard và Tarzia nhận thấy rằng "các công cụ trong vật lý thống kê đã được phát triển để nghiên cứu các pha vật lý chuyển tiếp có thể giúp trong việc xây dựng các thuật toán hiệu quả để giải các bài toán tổ hợp", thu thập từ các bước tính về các tính chất ở mức năng lượng cơ bản của các hệ vật lý chất rắn, dẫn đến phương pháp truyền -thăm dò (survey-propagation method). "Mézard và Tarzia sử dụng phương pháp này để tìm hiểu các tính chất thống kê trong các nghiệm của một số trường hợp cá biệt ở bài toán HSP. Điều này còn khó hơn cả so với việc tìm một nghiệm cụ thể, nhưng phương pháp truyền -thăm dò trên biên của một pha, có thể thu thập được các thông tin cần thiết." bằng thuật toán hồi quy của một tập hợp lớn các phương trình cặp, mô hình các tương tác địa phương giữa các biến một cách xác suất. Quá trình tìm nghiệm này có thể được thực hiện bằng phương pháp tính song song, do vậy có thể nhận được kết quả từ nhiều nhà toán học khác, nghiệm sẽ hội tụ sớm hớn trong một thời gian tính tương đối ngắn - chỉ vài giây cho các phương trình với hàng ngàn biến."
Nguồn: Hội Toán Học Mỹ (AMS)