Algoritmos exactos de tiempo exponencial para programación 0-1

¿Existen algoritmos conocidos para el siguiente problema que superen al algoritmo ingenuo?

Entrada: Un sistema de desigualdades lineales.$Ax \le b$$m$

Salida: una solución factible si existe.$x^*\in \{0,1 \}^n$

Supongamos que y tienen entradas enteros. Estoy interesado en los peores casos.$A$$b$

Si es superlineal, dicho algoritmo refutaría la hipótesis del tiempo exponencial fuerte, ya que las fórmulas en forma conjuntiva normal son un caso especial de programación 0-1 y el Lema de dispersión nos permite reducir -SAT a CNF-SAT en muchas cláusulas linealmente .$m$$k$

Sin embargo, existe un algoritmo debido a Impagliazzo, Paturi y a mí que puede resolver dicho sistema de desigualdades si el número de cables, es decir, el número de coeficientes distintos de cero en es lineal. En particular, si el número de cables es , el algoritmo se ejecuta en el tiempo , donde .c n 2 ( 1 - s ) n s = $A$$cn$$2^{(1-s)n}$$s=\frac1{c^{O(c^2)}}$

Si es lo suficientemente pequeño, puede hacerlo mejor que el algoritmo ingenuo, es decir, mejor que tiempo. Aquí "lo suficientemente pequeño" significa que es más pequeño que algo como . El tiempo de ejecución seguirá siendo exponencial, por ejemplo, podría ser tiempo, pero será más rápido que el algoritmo ingenuo.2 n m n / lg n 2 n /$m$$2^n$$m$$n/\lg n$$2^{n/2}$

Por cierto, parece que esto nos permite resolver el problema en más de tiempo en algunos casos en los que la matriz tiene un número de entradas súper lineal. No sé cómo cuadrar eso con la otra respuesta proporcionada aquí. En consecuencia, debe verificar mi respuesta cuidadosamente: podría indicar que he cometido un grave error en alguna parte.$2^n$$A$

El enfoque básico: escribir , donde contiene los primeros componentes de y contiene los últimos componentes; y de forma similar , donde tiene las columnas izquierdas de y las columnas derechas . Ahora puede reescribirse en el formulariox 0 n / 2 x x 1 n / 2 A = ( A 0 , A 1 ) A 0 n / 2 A A 1 n / 2 A x ≤ $x=(x_0,x_1)$$x_0$$n/2$$x$$x_1$$n/2$$A=(A_0,A_1)$$A_0$$n/2$$A$$A_1$$n/2$$Ax \le b$

o equivalente,

Enumere todas las posibilidades para , y deje que denote el conjunto de valores posibles, es decir,$2^{n/2}$$A_0 x_0$$S$

Del mismo modo, enumere el conjunto de todas las posibilidades para , es decir,$T$$2^{n/2}$$b - A_1 x_1$

Ahora el problema se vuelve

Dados los conjuntos de tamaño , ¿existe y tal que ?$S,T \subseteq \mathbb{Z}^{m}$$2^{n/2}$$s\in S$$t \in T$$s\le t$

(Aquí es tomada por puntos, es decir, es necesario que para toda .)$\le$$s_i \le t_i$$i$

El último problema se discute en CS.StackExchange , y aparentemente hay un algoritmo que se ejecuta en el tiempo . Si es suficientemente pequeño (digamos, más pequeño que ), entonces se deduce que el tiempo total de ejecución será menor que , según se desee.$O(2^{n/2} (n/2)^{m-1})$$m$$n/\lg n$$2^n$

Para ayudar a que este resultado parezca más plausible, aquí hay una intuición muy cruda. Si tomamos el caso extremo donde , por supuesto, esto se puede resolver rápidamente. (En realidad, hay un algoritmo mucho más simple para el caso especial donde : sea si , de lo contrario ; ahora si existe alguna solución factible, entonces esta será una. )m = 1 x i = 1 A 1 , i ≤ 0 x i = 0 $m=1$$m=1$$x_i=1$$A_{1,i}\le 0$$x_i=0$$x$