Si el número de coeficientes distintos de cero en A es lineal en n , existe un algoritmo que resuelve este problema en menos de 2n tiempo.
Así es como funciona. Usamos la conexión estándar entre un problema de optimización y su correspondiente problema de decisión. Para probar si existe una solución donde y , formaremos un problema de decisión: adjuntaremos la restricción a la matriz , y probaremos si existe alguna tal que y . En particular, formaremos una nueva matriz tomando y agregando una fila adicional que contenga , y formaremos tomandoxAx≤bcTx≥αcTx≥αAxAx≤b−cTx≤−αA′A−cTb′by junto a una fila adicional con . Obtenemos un problema de decisión: ¿existe tal que ? La respuesta a este problema de decisión nos dice si existe una solución al problema de optimización original de valor o mayor. Además, como se explica en la respuesta a su pregunta anterior , este problema de decisión se puede resolver en menos de tiempo, si el número de coeficientes distintos de cero en es lineal en (y, por lo tanto, si el número de coeficientes cero en es lineal en ). Ahora podemos usar la búsqueda binaria en−αx∈{0,1}nA′x≤b′α2nA′nAnαpara resolver su problema de optimización en menos de tiempo.2n
Agradezco a AustinBuchanan y Stefan Schneider por ayudar a depurar una versión anterior de esta respuesta.
¿Puede dar una respuesta más fuerte: como "hay un algoritmo de tiempo " o "un algoritmo más rápido de lo que refutaría ..."? O ( 2 n )O(2n/2)O(2n)
Austin Buchanan
@AustinBuchanan, si el número de dimensiones de es lo suficientemente pequeño, hay un algoritmo , como se documenta en mi respuesta a la otra pregunta . Eso es lo mejor que sé hacer; No sé cómo hacerlo mejor que eso. ¡Quizás otros puedan proporcionar una respuesta más fuerte! O ∗ ( 2 n / 2 )bO∗(2n/2)
DW
O ( 1 )O∗(2n/2) tiempo se detiene cuando el número de restricciones es ? O(1)
Austin Buchanan
4
Si consideramos el problema de minimización , entonces la siguiente reducción muestra que un algoritmo se ejecuta en el tiempo para refutaría el SETH. Una reformulación demuestra el mismo resultado para el problema deseado (la versión de maximización).O ( 2 δ n / 2 ) δ < 1miny{cTy:Ay≥b,y∈{0,1}n}O(2δn/2)δ<1
Dada una instancia de CNF-SAT con variables , formule una IP 0-1 con dos variables para cada variable en la instancia SAT. Como de costumbre, la cláusula se representaría como . Luego, para cada variable en la instancia SAT, agregue una restricción . El objetivo es minimizar . El objetivo de la IP será si la instancia SAT es satisfactoria.Φ=∧mi=1Ci{xj}nj=1yj,y¯¯¯jxj(x1∨x¯¯¯2∨x3)y1+y¯¯¯2+y3≥1xjyj+y¯¯¯j≥1n∑nj=1(yj+y¯¯¯j)n
Gracias a Stefan Schneider por la corrección.
Actualización: en Problemas tan difíciles como CNF-Sat, los autores conjeturan que SET COVER no se puede resolver en el tiempo , , donde refiere al número de conjuntos. Si es cierto, esto demostraría que mi problema no puede resolverse en el tiempo también.δ < 1 n O ( 2 δ n )O(2δn)δ<1nO(2δn)
Actualización 2. Por lo que puedo decir, suponiendo que SETH, mi problema no se puede resolver en el tiempo , ya que se ha demostrado que Hitting Set (con un conjunto de tierra de tamaño ) no se puede resolver resuelto en el tiempo .n O ( 2 δ n )O(2δn)nO(2δn)
Como duplica el número de variables, creo que esto solo muestra que un algoritmo para este problema con el tiempo de ejecución contradeciría SETH. O(2δn/2)
Stefan Schneider
Espere ... los autores de On Problems as Hard as CNF-SAT afirman que "por cada , un algoritmo para golpear Set violaría SETH". ¿Esto no funciona? O ( 2 ϵ n ) ...ϵ<1O(2ϵn)…
Si consideramos el problema de minimización , entonces la siguiente reducción muestra que un algoritmo se ejecuta en el tiempo para refutaría el SETH. Una reformulación demuestra el mismo resultado para el problema deseado (la versión de maximización).O ( 2 δ n / 2 ) δ < 1miny{cTy:Ay≥b,y∈{0,1}n} O(2δn/2) δ<1
Dada una instancia de CNF-SAT con variables , formule una IP 0-1 con dos variables para cada variable en la instancia SAT. Como de costumbre, la cláusula se representaría como . Luego, para cada variable en la instancia SAT, agregue una restricción . El objetivo es minimizar . El objetivo de la IP será si la instancia SAT es satisfactoria.Φ=∧mi=1Ci {xj}nj=1 yj,y¯¯¯j xj (x1∨x¯¯¯2∨x3) y1+y¯¯¯2+y3≥1 xj yj+y¯¯¯j≥1 n∑nj=1(yj+y¯¯¯j) n
Gracias a Stefan Schneider por la corrección.
Actualización: en Problemas tan difíciles como CNF-Sat, los autores conjeturan que SET COVER no se puede resolver en el tiempo , , donde refiere al número de conjuntos. Si es cierto, esto demostraría que mi problema no puede resolverse en el tiempo también.δ < 1 n O ( 2 δ n )O(2δn) δ<1 n O(2δn)
Actualización 2. Por lo que puedo decir, suponiendo que SETH, mi problema no se puede resolver en el tiempo , ya que se ha demostrado que Hitting Set (con un conjunto de tierra de tamaño ) no se puede resolver resuelto en el tiempo .n O ( 2 δ n )O(2δn) n O(2δn)
fuente