Ridurre il seguente problema a SAT

Question

Qui è il problema. Dato $ k, n, T_1, \ ldots, T_M $, in cui ogni $ t_i \ subseteq \ {1, \ ldots, n \} $. Esiste un sottoinsieme $ S \ subseteq \ {1, \ ldots, n \} $ con dimensioni al massimo $ k $ tali che $ S \ cap t_i \ neq \ emptyset $ per tutti i $ i $? Sto cercando di ridurre questo problema a SAT. La mia idea di una soluzione potrebbe essere quella di avere una variabile $ x_i $ per ognuno di 1 a $ n $. Per ogni $ t_i $, creare una clausola di $ (x_ {I_1} \ vee \ cdots \ vee x_ ??{i_k}) $ se $ t_i = \ {I_1, \ ldots, i_k \} $. Poi e tutte queste clausole insieme. Ma questo chiaramente non è una soluzione completa in quanto non rappresenta il vincolo che $ S $ deve avere al massimo $ k $ elementi. So che devo creare più variabili, ma non sono sicuro di come semplicemente. Così ho due domande:

1. è la mia idea di una soluzione sulla strada giusta?
2. Come dovrebbero le nuove variabili essere creati in modo che possano essere utilizzati per rappresentare la cardinalità $ k $ vincolo?

Answer 1

Sembra che si sta tentando di calcolare un ipergrafo trasversale di dimensioni $ k $. Cioè, $ \ {T_1, \ dots, T_M \} $ è il tuo ipergrafo, e $ S $ è il tuo trasversale. Una traduzione standard è di esprimere le clausole come si deve, e poi tradurre la limitazione di lunghezza in un vincolo di cardinalità.

Quindi, utilizzare la codifica esistente, vale a dire, $ \ bigwedge_ {1 \ le j \ le m} \ bigvee_ {i \ in T_j} x_i $ e quindi aggiungere clausole che codificano per $ \ sum_ {1 \ le i \ le n} x_i \ le k $.

$ \ sum_ {1 \ le i \ le n} x_i \ le k $ è un vincolo di cardinalità. Ci sono vari diverse traduzioni vincolo di cardinalità in SAT.

La traduzione più semplice, ma piuttosto grande vincolo di cardinalità è di soli $ \ bigwedge_ {X \ subseteq \ {1, \ dots, n \}, | X | = K + 1} \ bigvee_ {i \ in X} \ neg x_i $. In questo modo ogni disgiunzione rappresenta il vincolo di $ \ neg \ bigwedge_ {i \ in X} x_i $ - per tutti i sottoinsiemi $ X $ di $ \ {1, \ dots, n \} $ di dimensione k + 1. Cioè, ci assicuriamo che non c'è modo che più di k variabili possono essere impostate. Nota che questo non è la dimensione polinomiale in $ k $

Alcuni link a documenti su più traduzioni vincolo di cardinalità di spazio-efficiente che sono dimensioni polinomio in $ k $ :

• Tradurre Vincoli Pseudo-booleani in SAT - Niklas Eén e Niklas Sörensson, JSAT vol 2 (2006), pg 1-26 (un sondaggio buono).
• efficiente CNF codifica dei booleani cardinalità vincoli - Olivier Bailleux e Yacine Boufkhad, Proceedings of Principles e la pratica di vincolo di programmazione 2003 LNCS vol 2833, pg 108-122 (una bella, abbastanza facile da implementare traduzione).
• Verso un'ottimale CNF codifica di booleana cardinalità Vincoli - Carsten Sinz - Proceedings of Principles and Practice di vincolo di programmazione 2005 LNCS 3709, pag 827-831.
• Verso robuste CNF codifiche di cardinalità Vincoli - Joao Marques-Silva e Inês Lynce, Atti di Principi e pratica di vincolo di programmazione 2007 LNCS 4741, pag 483-497.

Se si sono effettivamente interessati a risolvere tali problemi, forse è meglio per formulare loro come problemi pseudo-booleana (vedi wiki articolo sui problemi pseudo-booleana ) e sull'uso di solutori pseudo-booleana (vedi pseudo-booleano concorrenza ). In questo modo i vincoli di cardinalità sono solo vincoli pseudo-booleano e fanno parte del linguaggio -. Speriamo che il risolutore pseudo-booleana poi li gestisce direttamente e quindi in modo più efficiente

Answer 2

Se non si è assolutamente imposta sul normale SAT, la tua idea è già una riduzione di MIN-One (oltre le formule CNF positivi), che è fondamentalmente SAT, ma dove è possibile impostare al massimo $ k $ variabili true (rigorosamente è la versione di ottimizzazione in cui riduciamo al minimo il numero di veri variabili).

Allo stesso modo se si testa in una direzione parametrizzato Complessità, WSAT allora hai già praticamente ottenuto ($ \ Gamma_ {2,1} ^ {+} $), dove $ \ Gamma_ {2,1} ^ {+} $ è la classe di tutte le formule CNF positivi (come prima, la notazione potrebbe aiutare le vostre indagini però). In questo caso si avrebbe dovuto cominciare a guardare a ciò che la parametrizzazione sarebbe utile nel vostro caso.

I assumere siete alla ricerca di una riduzione di esplicito, ma in caso contrario, si può sempre e solo ripiegare al Cook-Levin Teorema .