Geek asks and answers

Subset inference np-complete?

Consider the following task:

There are N coins with numbers from 1 to N.

You cannot see them, but they are given M facts about the form:

struct Fact
{
    set<int> positions
    int num_heads
}

positionsidentifies a subset of coins, and num_heads- the number of coins in this subset, which are heads.

Given these facts, you need to determine the maximum number of goals that can be.

Is this problem NP-complete? If so, what is the reduction? If not, then what is a polynomial time solution?

For instance:

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

A configuration with most heads that matches the facts:

T H H T H

So, the answer is 3 heads.

+5
source share
3 answers

, 3-SAT. v . "true (v)" "false (v)". , v 3-SAT , " (v)" - ; "false (v)" - . v

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

3-SAT l1, l2, l3

l1 or l2 or l3


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

t/f (l1) " (l1)", "false (l1)" , l1 ( ) () . , " 1 " , " 1 " . . C1, C2, C3 - , " - ". X1, X2, X3

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

X1, X2, X3. , C1, C2, C3 ; X1..3 .

, " " ; head/tails , , 3-SAT .

3-SAT , , NP-. , NP-complete, , , QED.

+2

- 3SAT ( - ?), NP. NP-hard ( , ), , : , , , , - , - .

+1

- , , , . , .

0

More articles:


All Articles