Considere o problema de maximizar o número de equações lineares satisfeitas sobre algum anel R , que geralmente é NP-difícil, por exemplo, no caso R = ZMAX-LIN(R)RR=Z
Tome uma instância desse problema, onde A é uma matriz n × m . Seja k = m + 1 . Construa um novo sistema linear ˜ A ˜ x = ˜ b , onde ˜ A é uma matriz k n × ( k n + m ) , ˜ x agora é um vetor dimensional ( k n + m ) , e ˜ bAx=bAn×mk=m+1A~x~=b~A~kn×(kn+m)x~(kn+m)b~é um vetor dimensional :kn
Note-se que este sistema é sempre satisfeita pelo vector . Na verdade, os primeiros m entradas de ~ x pode ser arbitrária, e há algum vector da solução com que prefixo.x~=(0bb⋯b)Tmx~
Eu agora afirmar que fracção de equações de A x = b são sse satisfatível existe um escasso solução de ~ A ~ x = ~ b , que tem, pelo menos, ô n k zeros. Isso ocorre porque toda linha satisfeita de A x = b produz k zeros em potencial quando x é estendido para ˜ xδAx=bA~x~=b~δnkAx=bkxx~
Assim, se encontrar a dispersão da solução sparsest para , temos também maximizada δ , dividindo-se a dispersão por k .A~x~=b~δk
Legal! Obrigado por compartilhar. Então, o que você acha que a dependência está em c? Você acha que pode resolvê-lo em menos de ondené o tamanho da entrada? poly(n)⋅(nc)n
Michael Wehar
1
Claro: se assumirmos que elementos de x são zero, você pode simplesmente remover esses elementos de x para obter uma dimensão menor x ' e também remover as colunas correspondentes de A para obter A ' . Em seguida, use a eliminação gaussiana para decidir se o sistema reduzido A ′ x ′ = b é viável; se for, você encontrou uma solução esparsa. Então, você tenta tudo ( ncxxx′AA′A′x′=b possívelA′x(nc) . A′x′
Joe Bebel
1
@MichaelWehar Eu não sei se este problema é FPT ou não embora
Joe Bebel
6
O problema é NP-completo, por redução do seguinte problema: Dada uma matriz A com entradas inteiras e um vetor inteiro b com nm×nAbn entradas, existe um vetor 0-1 com A x = b ?xAx=b
Para cada coordenada do vetor x , xix
introduza novas equações x i + y i , k = 0 com k = 1 , …100(n+m)xi+yi,k=0 e k=1,…,100(n+m)
introduza novas equações x i + z i , k = 1 com k = 1 , …100(n+m)xi+zi,k=1 . k=1,…,100(n+m)
Além disso, use o antigo sistema de equações .Ax=b
Existe uma solução de 0-1 para o sistema original , se e somente se o novo sistema tiver uma solução na qual pelo menos 100 ( n + m ) n variáveis sejam zero.Ax=b100(n+m)n
Esse problema é difícil , em várias configurações. Como indicado nas outras respostas a esta pergunta, o problema é NP-completo sobre os números inteiros.
No processamento de sinais, a matriz e os vetores têm entradas racionais, e esse problema às vezes é chamado de problema de reconstrução esparsa . Nesta configuração, o problema é NP-completo (consulte o Teorema 1).
Na teoria da codificação, as entradas são de um campo finito e esse problema às vezes é chamado de problema de decodificação de probabilidade máxima . Nesse cenário, o problema é NP-completo e não no tempo subexponencial , assumindo a hipótese do tempo exponencial. Além disso, de acordo com uma versão anterior de um artigo sobre o arXiv (consulte o Lema C.2 na versão 1 do artigo), o problema é W [1] - completo.
Sua referência à completude W [1] não parece ter um "Lema C.2".
@RickyDemer Existe um Lemma C.2 na versão 1 do artigo que ele vinculou. No entanto, a versão 2 parece ter um título diferente e foi alterada muito recentemente.
22815 Michael Wehar
Esse lema usa uma parametrização diferente do OP.
Ah, eu não sabia que havia uma versão atualizada, vou dar uma olhada e atualizar minha resposta de acordo.
Argentpepper
Como mencionei no meu comentário anterior, que "o lema usa uma parametrização diferente do OP", portanto, mesmo se assumirmos que o resultado é verdadeiro (apesar de ter sido removido da versão 2), a pergunta do OP sobre complexidade parametrizada ainda estaria em aberto.
O problema é NP-completo, por redução do seguinte problema: Dada uma matriz A com entradas inteiras e um vetor inteiro b com nm×n A b n entradas, existe um vetor 0-1 com A x = b ?x Ax=b
Para cada coordenada do vetor x ,xi x
Além disso, use o antigo sistema de equações .Ax=b
Existe uma solução de 0-1 para o sistema original , se e somente se o novo sistema tiver uma solução na qual pelo menos 100 ( n + m ) n variáveis sejam zero.Ax=b 100(n+m)n
fonte
Isso é chamado de problema do vetor de solução mais escassa e , na verdade, é difícil para o NP .
fonte
Esse problema é difícil , em várias configurações. Como indicado nas outras respostas a esta pergunta, o problema é NP-completo sobre os números inteiros.
No processamento de sinais, a matriz e os vetores têm entradas racionais, e esse problema às vezes é chamado de problema de reconstrução esparsa . Nesta configuração, o problema é NP-completo (consulte o Teorema 1).
Na teoria da codificação, as entradas são de um campo finito e esse problema às vezes é chamado de problema de decodificação de probabilidade máxima . Nesse cenário, o problema é NP-completo e não no tempo subexponencial , assumindo a hipótese do tempo exponencial. Além disso, de acordo com uma versão anterior de um artigo sobre o arXiv (consulte o Lema C.2 na versão 1 do artigo), o problema é W [1] - completo.
fonte