Se for pequeno o suficiente, você poderá fazer melhor que o algoritmo ingênuo, ou seja, melhor que 2 n tempo. Aqui "pequeno o suficiente" significa que m é menor que algo como n / lg n . O tempo de execução ainda será exponencial - por exemplo, pode ser 2 n / 2 -, mas será mais rápido que o ingênuo algoritmo.m2nmn/lgn2n/2
Aliás, parece que isso nos permite resolver o problema em mais de tempo para alguns casos em que a matriz A possui um número super-linear de entradas. Não sei como combinar isso com a outra resposta fornecida aqui. Conseqüentemente, você deve verificar minha resposta com cuidado: isso pode indicar que cometi um erro grave em algum lugar.2nA
A abordagem básica: escreva , onde x 0 contém os primeiros n / 2 componentes de x e x 1 contém os últimos n / 2 componentes; e similarmente A = ( A 0 , A 1 ) , onde A 0 tem as n / 2 colunas esquerdas de A e A 1 a n direitax=(x0,x1)x0n/2xx1n/2A=(A0,A1)A0n/2AA1 colunas. Agora A x ≤ b pode ser reescrito no formaton/2Ax≤b
A0x0+A1x1≤b,
ou equivalente,
A0x0≤b−A1x1.
Enumere todas as possibilidades n / 2 para A 0 x 0 e deixe S denotar o conjunto de valores possíveis, ou seja,2n/2A0x0S
S={A0x0:x0∈{0,1}n/2}.
Da mesma forma, enumere o conjunto de todas as 2 n / 2 possibilidades de b - A 1 x 1 , ou seja,T2n/2b−A1x1
T={b−A1x1:x1∈{0,1}n/2}.
Agora o problema se torna
Conjuntos dados de tamanho 2 n / 2 não existem, s ∈ S e t ∈ T de tal forma que s ≤ t ?S,T⊆Zm2n/2s∈St∈Ts≤t
(Aqui é tomado em sentido horário, ou seja, exigimos que s i ≤ t i para todos os i .)≤si≤tii
O último problema é discutido no CS.StackExchange e, aparentemente, existe um algoritmo para ele que é executado no tempo . Se m for suficientemente pequeno (por exemplo, menor que n / lg n ), então o tempo total de execução será menor que 2 n , conforme desejado.O(2n/2(n/2)m−1)mn/lgn2n
Para ajudar a tornar esse resultado mais plausível, aqui está uma intuição muito grosseira. Se considerarmos o caso extremo em que , é claro que isso pode ser resolvido rapidamente. (Na verdade, há um algoritmo muito mais simples para o caso especial em que m = 1 : deixar x i = 1 se A 1 , i ≤ 0 , caso contrário, x i = 0 ; agora se qualquer solução viável existe, então este x . Irá ser um)m=1m=1xi=1A1,i≤0xi=0x