5
Tôi biết rằng sự thỏa mãn boolean là NP-Complete, nhưng là giảm thiểu/đơn giản hóa một biểu thức boolean, theo đó tôi có nghĩa là dùng một biểu thức nhất định ở dạng biểu tượng và tạo ra một biểu thức tương đương nhưng đơn giản dưới dạng ký hiệu, NP-Complete? Tôi không chắc rằng có một sự giảm từ sự thỏa mãn để giảm thiểu, nhưng tôi cảm thấy có lẽ có. Có ai biết chắc chắn?Giảm thiểu các biểu thức boolean NP-Complete?
Được viết gọn gàng hơn một chút, đây có thể là mức giảm mà anh đang tìm kiếm. –
Bạn và áp phích gốc có thể có nghĩa là NP-hard. Theo như tôi có thể tìm ra vấn đề không được biết là trong NP. – starblue
starblue: không, chúng tôi có nghĩa là NP hoàn thành. SAT thực sự là vấn đề NP hoàn chỉnh cổ điển, tức là vấn đề đầu tiên đã được chứng minh là NP hoàn thành, và tất cả những vấn đề khác được giảm trực tiếp hoặc gián tiếp. Điều này, bằng cách này, là tất cả giải thích trong bài viết Wikipedia. –