Suy luận tập hợp NP-complete?

Question

Hãy xem xét những vấn đề sau đây:

Có N đồng tiền đánh số từ 1 đến N.

Bạn không thể nhìn thấy chúng, nhưng được cho sự kiện M về chúng có dạng:

struct Fact 
{ 
    set<int> positions 
    int num_heads 
} 

positions xác định một tập hợp con của các đồng tiền, và num_heads là số lượng tiền trong tập con đó là đầu.

Với những sự kiện M này, bạn cần phải tính toán số lượng người đứng đầu tối đa có thể có.

Sự cố này có hoàn thành NP không? Nếu có, mức giảm là bao nhiêu? Nếu không, giải pháp thời gian đa thức là gì?

Ví dụ:

N = 5 
M = 3 
fact1 = { {1, 2}, 1 } // Either coin 1 or coin 2 is a head 
fact2 = { {4}, 0 } // Coin 4 is a tail 
fact3 = { {2, 4, 5}, 2 } // Out of coins 2, 4 and 5, two are heads 

Một cấu hình với hầu hết người đứng đầu phù hợp với thực tế là:

T H H T H 

Vì vậy, câu trả lời là 3 người đứng đầu.

Answer 1

Giả sử bạn gặp sự cố 3-SAT. Bạn có thể ánh xạ mọi biến boolean v trong vấn đề đó thành hai đồng xu. Gọi chúng là 'true (v)' và 'false (v)'. Ý tưởng là nếu v trong một giải pháp cho vấn đề 3-SAT là đúng, thì 'true (v)' là đầu; nếu không thì 'false (v)' là phần đầu. Đối với mỗi v bạn thêm các hạn chế xu

{true(v), false(v)} has 1 heads, and has 1 tails 

Sau đó, bạn có thể dịch một điều khoản với literals L1, L2, L3

l1 or l2 or l3 

3-SAT để đồng tiền chế

{t/f(l1), t/f(l2), t/f(l3)} has at least 1 heads 

trong đó t/f (l1) hoặc là 'true (l1)' hoặc 'false (l1)' tùy thuộc vào nếu l1 là dương (không phủ định) hoặc âm (phủ định) trong mệnh đề. Chúng tôi chỉ cần chứng minh rằng 'ít nhất 1 người đứng đầu' có thể được thực hiện trong vấn đề tiền xu là 'ít nhất 1 người đứng đầu' không thể diễn đạt trực tiếp. Điều này có thể được thực hiện với các thiết bị sau đây. Hãy để C1, C2, C3 là ba đồng xu mà chúng ta muốn nêu ra ràng buộc 'ít nhất một trong số chúng là đầu'. Tạo ba đồng tiền khác X1, X2, X3 và đặt trong ràng buộc

{X1, X2, X3, C1, C2, C3} has 4 heads 

nhưng không có ràng buộc nào khác đối với X1, X2, X3. Ràng buộc này chỉ được thỏa mãn nếu ít nhất một trong các C1, C2, C3 là các đầu; các đồng tiền X1.3 có thể được sử dụng để cung cấp cho những người đứng đầu cần thiết còn lại.

Lưu ý rằng việc giảm này không sử dụng khía cạnh "số lượng người đứng đầu tối đa" của vấn đề; hoàn toàn không thể chọn trạng thái đầu/đuôi cho các đồng tiền đại diện cho các biến boolean nếu công thức 3-SAT không thỏa mãn.

Đây là sự giảm đa thức TỪ 3-SAT đối với vấn đề đồng xu của bạn, cho thấy đó là NP-hard. Để hiển thị nó là NP-hoàn thành, chỉ cần quan sát rằng một giải pháp cho vấn đề tiền xu của bạn có thể được kiểm tra trong thời gian đa thức, QED.

Answer 2

One-in-three 3SAT giảm thiểu tầm quan trọng đối với phiên bản quyết định của sự cố của bạn (có tồn tại cấu hình nào không?), Điều này là không đáng kể trong NP.Phiên bản tối đa là NP- cứng (nhưng không hoàn chỉnh vì nó không phải là vấn đề quyết định), ngay cả phiên bản hứa hẹn phải có cấu hình thỏa mãn: thêm vào đầu ra của quyết định giảm thêm một đồng xu xuất hiện trong tất cả các tập con, tạo ra một giải pháp cực kỳ tồi tệ, nơi mà đồng xu đó là người đứng đầu và tất cả những người khác đều là đuôi.

Answer 3

Kết hợp hoàn hảo có sự giảm đơn giản đối với vấn đề này - biểu thị các cạnh là tiền xu, cho mỗi đỉnh trong biểu đồ tạo ra một thực tế quy định chính xác một trong các cạnh ngẫu nhiên là đầu. Kết hợp hoàn hảo trong biểu đồ gốc tồn tại nếu và chỉ khi có giải pháp bằng tiền xu.