Reduce el siguiente problema a SAT

21

Aquí está el problema. Dado , donde cada T i{ 1 , ... , n } . ¿Hay un subconjunto S { 1 , ... , n } con un tamaño máximo de k tal que S T i para todo i ? Estoy tratando de reducir este problema a SAT. Mi idea de una solución sería tener una variable x ik,n,T1,,TmTi{1,,n}S{1,,n}kSTiixipara cada uno de 1 a . Para cada T i , cree una cláusula ( x i 1x i k ) si T i = { i 1 , ... , i k } . Entonces y todas estas cláusulas juntas. Pero esto claramente no es una solución completa ya que no representa la restricción que S debe tener como máximo k elementos. Sé que debo crear más variables, pero simplemente no estoy seguro de cómo. Entonces tengo dos preguntas:nTi(xi1xik)Ti={i1,,ik}Sk

  1. ¿Está mi idea de solución en el camino correcto?
  2. ¿Cómo deben crearse las nuevas variables para que puedan usarse para representar la restricción de cardinalidad ?k
Aden Dong
fuente
55
Solo una observación: su problema se conoce como HITTING SET , que es una formulación equivalente del problema SET COVER .
A.Schulz

Respuestas:

13

Parece que está tratando de calcular una hipergrafía transversal de tamaño . Es decir, { T 1 , ... , T m } es su hipergrafía, y S es su transversal. Una traducción estándar es expresar las cláusulas como lo ha hecho, y luego traducir la restricción de longitud en una restricción de cardinalidad.k{T1,,Tm}S

Por lo tanto, utilice su codificación existente, es decir, y luego agregue cláusulas que codifiquen 1 i n x ik .1jmiTjxi1inxik

es una restricción de cardinalidad. Hay varias traducciones de restricciones de cardinalidad diferentes al SAT.1inxik

La traducción de restricción de cardinalidad más simple pero bastante grande es solo . De esta manera, cada disyunción representa la restricción ¬ i X x i - para todos los subconjuntos X de { 1 , ... , n }X{1,,n},|X|=k+1iX¬xi¬iXxiX{1,,n}de tamaño k + 1. Es decir, nos aseguramos de que no haya forma de que se puedan establecer más de k variables. Tenga en cuenta que este no es un tamaño polinómico en k

Algunos enlaces a documentos sobre traducciones de restricciones de cardinalidad más eficientes en espacio que son de tamaño polinómico en k :

Si realmente está interesado en resolver tales problemas, tal vez sea mejor formularlos como problemas pseudo-booleanos (vea el artículo wiki sobre problemas pseudo-booleanos ) y use solucionadores pseudo-booleanos (vea competencia pseudo-booleana ). De esa manera, las restricciones de cardinalidad son solo restricciones pseudobooleanas y son parte del lenguaje; es de esperar que el solucionador pseudobooleano las maneje directamente y, por lo tanto, de manera más eficiente.

MGwynne
fuente
1
Describa todos los enlaces en breve (al menos autor y título) para que las personas puedan encontrar los documentos en caso de que los enlaces se rompan. Probablemente sea mejor usar DOI si está disponible.
Raphael
1
@Raphael Buen punto! Disculpas, debería haber hecho eso para empezar. Ahora he actualizado todos los enlaces; No estoy seguro de si Springer proporciona DOI, pero ahora debería haber suficiente información para encontrarlos si se rompen los enlaces. Nota: no hago enlaces a los archivos PDF oficiales de Springer para evitar problemas de acceso.
MGwynne
Pero parece que la reducción que diste no está en el tiempo polinómico, ¿verdad?
Aden Dong
@AdenDong No dijiste nada sobre polinomio;). La traducción de restricción de cardinalidad simple que menciono no es polinomial en (pero es para k fija ). Las traducciones de restricción de cardinalidad dadas en los trabajos que enumero son polinomiales en k , usando nuevas variables. He actualizado mi respuesta para aclarar esto. kkk
MGwynne
MGwynne, tiendo a vincular siempre el DOI oficial, incluso si tiene un pago para ser a prueba de futuro y, además, versiones gratuitas. Pero como es ahora, cualquiera debería poder encontrar los papeles, así que está completamente bien.
Raphael
6

k

Γ2,1+Γ2,1+

Supongo que está buscando una reducción explícita, pero si no, siempre puede recurrir al Teorema de Cook-Levin .

Luke Mathieson
fuente