Inferenza sottoinsieme NP-completa?

Question

Si consideri il seguente problema:

ci sono n monete numerati da 1 a N.

Non potete vederli, ma sono dati M fatti su di loro nella forma:

struct Fact 
{ 
    set<int> positions 
    int num_heads 
} 

positions identifica un sottoinsieme delle monete e num_heads è il numero di monete in quel sottoinsieme che sono teste.

Dato questi fatti M è necessario calcolare il numero massimo di teste che potrebbero esserci.

Questo problema è NP-completo? Se sì, qual è la riduzione? Se no, qual è una soluzione temporale polinomiale?

Ad esempio:

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 

Una configurazione con il maggior numero di teste che corrisponde ai fatti è:

T H H T H 

Quindi la risposta è 3 teste.

Answer 1

Supponiamo di avere un problema 3-SAT. Puoi mappare ogni variabile booleana v in quel problema a due monete. Chiamali "vero (v)" e "falso (v)". L'idea è che se v in una soluzione al problema 3-SAT è vero, allora 'true (v)' è heads; altrimenti 'falso (v)' è la testa. Per ogni V si aggiunge il vincolo moneta

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

Dopo questo, è possibile tradurre una clausola di 3-SAT con letterali L1, L2, L3

l1 or l2 or l3 

al vincolo moneta

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

dove t/f (l1) è "vero (l1)" o "falso (l1)" a seconda che l1 sia positivo (non negato) o negativo (negato) nella clausola. Abbiamo solo bisogno di dimostrare che "almeno 1 teste" possono essere implementate nel problema delle monete poiché "almeno 1 teste" non è direttamente esplicabile. Questo può essere fatto con il seguente dispositivo. Lasciate che C1, C2, C3 siano tre monete per le quali vogliamo dichiarare il vincolo "almeno una di esse è testa". Creare altre tre monete X1, X2, X3 e mettere in vincolo

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

ma non altri vincoli per X1, X2, X3. Questo vincolo è soddisfatto solo se almeno uno di C1, C2, C3 è testa; le monete X1..3 possono essere utilizzate per fornire le restanti teste necessarie.

Si noti che questa riduzione non utilizza affatto l'aspetto "numero massimo di teste" del problema; è chiaramente impossibile scegliere lo stato di teste/code per le monete che rappresentano le variabili booleane se la formula 3-SAT non è soddisfacente.

Questa è una riduzione polinomiale DA 3-SAT AL tuo problema con le monete, dimostrando che è NP-difficile. Per dimostrarlo è NP-completo, basta osservare che una soluzione al problema delle monete può essere verificata in tempo polinomiale, QED.

Answer 2

One-in-three 3SAT si riduce banalmente alla versione decisionale del problema (esiste una configurazione?), Che è banalmente in NP.La versione di ottimizzazione è NP- hard (ma non completa perché non è un problema di decisione), anche la versione di promessa in cui deve esserci una configurazione soddisfacente: aggiungere all'output della riduzione di decisione una moneta in più che appare in tutti i sottoinsiemi, creando una brutta soluzione in più dove quella moneta è la testa e tutte le altre sono code.

Answer 3

L'abbinamento perfetto ha una riduzione diretta a questo problema - rappresenta i bordi come monete, poiché ogni vertice nel grafico crea un fatto che stabilisce che esattamente uno dei bordi accidentali è la testa. Un perfetto abbinamento nel grafico originale esiste se e solo se c'è una soluzione in monete.