Точные экспоненциально-временные алгоритмы для программирования 0-1

10

Существуют ли известные алгоритмы для следующей задачи, которые побеждают наивный алгоритм?

Вход: система из m линейных неравенств.Axbm

Вывод: выполнимое решение если оно существует.x{0,1}n

Предположим, что и b имеют целочисленные записи. Меня интересуют границы в худшем случае.Ab

Остин Бьюкенен
источник

Ответы:

14

Если является суперлинейным, такой алгоритм опровергает гипотезу сильного экспоненциального времени, поскольку формулы в конъюнктивной нормальной форме являются частным случаем программирования 0-1, а лемма о разрежении позволяет нам уменьшить k -SAT до CNF-SAT по линейному множеству предложений. ,mk

Acn2(1s)ns=1cO(c2)

Стефан Шнайдер
источник
1

m2nmn/lgn2n/2

2nA


x=(x0,x1)x0n/2xx1n/2A=(A0,A1)A0n/2AA1n/2Axb

A0x0+A1x1b,

или эквивалентно,

A0x0bA1x1.

2n/2A0x0S

S={A0x0:x0{0,1}n/2}.

T2n/2bA1x1

T={bA1x1:x1{0,1}n/2}.

Теперь проблема становится

S,TZm2n/2sStTst

sitii

O(2n/2(n/2)m1)mn/lgn2n


m=1m=1xi=1A1,i0xi=0x

DW
источник
1
Алгоритм из моего ответа также сводится к векторной проблеме, описанной в вашем ответе, с использованием того же метода, то есть разделить переменные и перечислить все их назначения.
Стефан Шнайдер
2
2O(m)